1. 项目概述从“零食奖励”看华为OD机试的算法思维最近在帮几个准备冲刺华为OD机试的朋友做模拟训练发现一个挺有意思的现象很多同学一看到“动态规划”、“图论”这些词就头疼觉得是“硬骨头”反而对一些看似生活化的题目掉以轻心。比如这道“零食奖励”标题听起来人畜无害好像是个简单的分配问题但真上手一写各种边界条件和状态转移的逻辑陷阱就都冒出来了。这道题是2025C卷的新题它考察的核心远不止是写对一个循环或者判断而是对贪心策略的深刻理解和对问题本质的抽象能力。今天我就结合这道题把C、Java、Python、C语言和JS五种语言的实现思路和代码细节都掰开揉碎了讲一遍更重要的是分享一套面对这类“场景应用题”的通用拆解方法。无论你是正在备战OD还是想巩固算法基础相信这篇从实战出发的深度解析都能给你带来不一样的启发。2. 核心需求与问题抽象2.1 题目场景还原与核心诉求我们先抛开代码把题目用大白话翻译一下。想象一个班主任要奖励班上一排坐着的小朋友零食。每个小朋友有一个“表现分”。奖励规则是公平原则每个小朋友至少得到1份零食。激励原则如果某个小朋友的表现分比相邻的小朋友高那么他得到的零食必须比那个相邻的小朋友多。我们的目标是在满足以上两条规则的前提下计算出需要准备的零食总数最少是多少。这本质上是一个约束优化问题。约束是规则1和2优化目标是“总数最小”。规则1给了我们一个基础值每人至少1个规则2则引入了变量使得我们不能再简单地给每人发1个了事。2.2 问题抽象与算法定位为什么说这道题“坑”多因为它完美地模拟了实际开发中产品经理给的一个看似简单的业务需求背后却需要精巧的设计。首先我们需要把“一排小朋友”抽象成一个整数数组scores数组的每个元素就是对应位置小朋友的表现分。我们的输出是另一个等长的数组rewards表示每个小朋友分到的零食数并且要满足rewards[i] 1公平原则如果scores[i] scores[i-1]那么rewards[i] rewards[i-1]左邻激励如果scores[i] scores[i1]那么rewards[i] rewards[i1]右邻激励在满足以上所有条件的前提下sum(rewards)最小。看到“相邻比较”和“最小总数”有经验的同学应该能立刻联想到经典的“分发糖果”问题。没错“零食奖励”就是这道经典题目的一个变体或直接应用。其标准解法是两次遍历的贪心算法。注意这里最容易犯的第一个错误是试图“一遍遍历搞定”。因为一个小朋友的零食数同时受左右两边邻居的影响只从左到右扫一遍无法处理“右边比左边高”但左边值还未确定的情况。必须把左右影响拆开处理。算法核心思想把“比邻居高则零食多”这个约束拆解成两个独立的子问题左规则当scores[i] scores[i-1]时保证rewards[i] rewards[i-1]。右规则当scores[i] scores[i1]时保证rewards[i] rewards[i1]。为了让总数最小我们在满足每个规则时都采取“最小幅度增加”的策略即只比邻居多1个。最后对于每个位置i为了同时满足左规则和右规则他最终得到的零食数rewards[i]应该是分别满足左规则和右规则时计算出的两个值的最大值。这个“取最大值”的操作是保证两个约束同时被满足的关键。3. 算法思路详解与多语言实现框架3.1 标准两次遍历贪心算法拆解理解了核心思想我们来看具体的步骤这是写出健壮代码的蓝图初始化创建一个长度与scores相同的数组rewards将所有元素初始化为1。这满足了“每人至少1个”的基础约束。第一次遍历从左到右处理“左规则”。从下标i 1开始遍历到数组末尾。如果scores[i] scores[i-1]那么为了满足左规则rewards[i]至少要比rewards[i-1]多1。我们采取最小化策略令rewards[i] rewards[i-1] 1。经过这次遍历我们确保了对于任何位置只要他比左边的邻居表现好他的零食数就一定比左边多。但此时还没有考虑右边邻居的影响。第二次遍历从右到左处理“右规则”。从下标i n-2开始倒数第二个遍历到数组开头i 0。如果scores[i] scores[i1]那么为了满足右规则rewards[i]至少要比rewards[i1]多1。同样我们取最小增量rewards[i] max(rewards[i], rewards[i1] 1)。这里为什么要用max因为rewards[i]在第一次遍历后可能已经有了一个值比如它比左边高这个值可能已经大于rewards[i1] 1。我们取两者中的较大者才能同时满足左规则如果存在和当前的右规则。计算结果遍历rewards数组求和即为所需的最少零食总数。这个算法的时间复杂度是 O(n)空间复杂度是 O(n)用于存储rewards数组。3.2 关键边界与陷阱分析在动手写代码前必须想清楚以下几个边界情况它们往往是测试用例的重点也是面试时考察你思维严密性的地方空数组或单元素数组如果小朋友人数为0总数应该是0。如果只有1个小朋友根据规则他至少得1个总数就是1。代码中需要对输入长度进行判断。分数相等的情况规则只说了“高于”才需要更多零食。如果分数相等是没有强制要求的。因此在两次遍历的判断条件中必须是严格大于而不是大于等于。这是很多同学容易忽略的细节。非严格递增/递减序列比如分数是[1, 2, 2, 3]。对于第一个2它比左边的1大所以rewards[1]变成2。第二个2它不比左边的2大所以rewards[2]保持为1。在从右向左遍历时第二个2比右边的3小所以规则不触发。最终第二个2的小朋友只得到1个零食而第一个2得到2个这是符合规则的分数相同零食数可以不同。这个例子很好地体现了算法的正确性。V型序列比如[1, 3, 2]。从左到右后rewards为[1, 2, 1]。从右到左时发现scores[1] (3) scores[2] (2)所以rewards[1]需要至少是rewards[2]12当前值已经是2满足。最终rewards[1]为2正确。4. 多语言代码实现与细节剖析接下来我们分别用五种语言实现上述算法。我会重点指出每种语言在实现时需要注意的语法特性和性能细节。4.1 C 实现C的实现需要关注容器选择、循环边界和标准库函数的使用。#include iostream #include vector #include algorithm // 用于max函数 #include numeric // 用于accumulate求和 using namespace std; int minRewards(vectorint scores) { int n scores.size(); if (n 0) return 0; if (n 1) return 1; vectorint rewards(n, 1); // 初始化每人至少1个 // 从左到右遍历满足左规则 for (int i 1; i n; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左遍历满足右规则并取最大值 for (int i n - 2; i 0; --i) { if (scores[i] scores[i 1]) { // 关键取当前值和满足右规则所需值的较大者 rewards[i] max(rewards[i], rewards[i 1] 1); } } // 计算总和 int total accumulate(rewards.begin(), rewards.end(), 0); return total; } int main() { // 示例测试 vectorint scores1 {1, 3, 2, 1, 4, 2}; // 可以自己计算验证 cout 最少零食数: minRewards(scores1) endl; vectorint scores2 {1, 2, 2}; // 相等分数测试 cout 最少零食数: minRewards(scores2) endl; return 0; }C实操要点容器选择使用vectorint是最通用和高效的选择。避免使用原生数组除非有极致的性能要求且长度固定。求和操作使用numeric中的std::accumulate是标准且安全的求和方式比手写循环更清晰。第三个参数0是求和的初始值也决定了返回类型int。循环变量使用前缀i而非后缀i对于内置类型虽然性能差异可忽略但这是一个良好的习惯尤其在涉及迭代器的泛型代码中。max函数直接使用std::max清晰明了。4.2 Java 实现Java的实现要注意数组操作、循环以及使用Math.max。public class SnackRewards { public static int minRewards(int[] scores) { if (scores null || scores.length 0) { return 0; } int n scores.length; if (n 1) { return 1; } int[] rewards new int[n]; // 初始化 for (int i 0; i n; i) { rewards[i] 1; } // 从左到右 for (int i 1; i n; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左 for (int i n - 2; i 0; i--) { if (scores[i] scores[i 1]) { rewards[i] Math.max(rewards[i], rewards[i 1] 1); } } // 求和 int total 0; for (int reward : rewards) { total reward; } return total; } public static void main(String[] args) { int[] scores1 {1, 3, 2, 1, 4, 2}; System.out.println(最少零食数: minRewards(scores1)); // 输出应为 10 int[] scores2 {1, 2, 2}; System.out.println(最少零食数: minRewards(scores2)); // 输出应为 4 } }Java实操要点空值判断Java中方法参数可能是null所以优先进行if (scores null)判断这是健壮性编程的基本要求。数组初始化int[] rewards new int[n];并不会自动初始化为1必须显式循环赋值。也可以使用Arrays.fill(rewards, 1)但手写循环更直观且性能无差异。求和Java中没有内置的数组求和工具方法除非用Stream但小题大做手写循环求和是最直接的方式。Math.max使用Math.max进行两者取大。4.3 Python 实现Python的代码非常简洁利用列表推导式和内置函数可以写得非常优雅。def min_rewards(scores): if not scores: return 0 n len(scores) if n 1: return 1 rewards [1] * n # 优雅的初始化 # 从左到右遍历 for i in range(1, n): if scores[i] scores[i - 1]: rewards[i] rewards[i - 1] 1 # 从右到左遍历 for i in range(n - 2, -1, -1): # 注意range的用法起点终点不含步长 if scores[i] scores[i 1]: # 使用max函数取较大值 rewards[i] max(rewards[i], rewards[i 1] 1) return sum(rewards) # 内置sum函数非常方便 # 测试 if __name__ __main__: scores1 [1, 3, 2, 1, 4, 2] print(f最少零食数: {min_rewards(scores1)}) # 输出 10 scores2 [1, 2, 2] print(f最少零食数: {min_rewards(scores2)}) # 输出 4Python实操要点列表初始化[1] * n是创建包含n个1的列表的最高效方式清晰且快速。反向遍历range(n-2, -1, -1)是经典的反向循环写法。起点是n-2倒数第二个索引终点是-1意味着要包含0步长为-1。也可以使用reversed(range(n-1))但不如直接指定range直观。求和sum(rewards)是Python的内置函数直接对可迭代对象求和代码简洁高效。条件判断if not scores:可以同时判断None和空列表是Pythonic的写法。4.4 C语言实现C语言的实现需要手动管理内存本例中不需要动态分配和循环更接近底层。#include stdio.h #include stdlib.h // 为了使用动态内存分配如果输入大小不定 // 假设scores数组和长度n已知rewards数组已分配好空间 int minRewards(int* scores, int scoresSize) { if (scoresSize 0) return 0; if (scoresSize 1) return 1; // 在栈上分配奖励数组如果数据量大可考虑动态分配 int* rewards (int*)malloc(scoresSize * sizeof(int)); if (rewards NULL) { return -1; // 分配失败返回错误码 } // 初始化 for (int i 0; i scoresSize; i) { rewards[i] 1; } // 从左到右 for (int i 1; i scoresSize; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左 for (int i scoresSize - 2; i 0; i--) { if (scores[i] scores[i 1]) { int newReward rewards[i 1] 1; rewards[i] (rewards[i] newReward) ? rewards[i] : newReward; // 三目运算符实现max } } // 求和 int total 0; for (int i 0; i scoresSize; i) { total rewards[i]; } free(rewards); // 释放动态分配的内存 return total; } int main() { int scores1[] {1, 3, 2, 1, 4, 2}; int size1 sizeof(scores1) / sizeof(scores1[0]); printf(最少零食数: %d\n, minRewards(scores1, size1)); int scores2[] {1, 2, 2}; int size2 sizeof(scores2) / sizeof(scores2[0]); printf(最少零食数: %d\n, minRewards(scores2, size2)); return 0; }C语言实操要点内存管理示例中使用了malloc动态分配rewards数组务必记得在函数返回前free否则会造成内存泄漏。这是C语言编程的核心纪律之一。数组长度传递C语言中数组作为参数会退化为指针必须同时传递数组长度scoresSize。max函数C标准库没有内置的max函数用于整型通常需要自己定义宏或者像示例中一样使用三目运算符(a b) ? a : b。错误处理malloc可能失败返回NULL。生产代码中必须检查并处理这种错误示例中简单返回了-1。4.5 JavaScript (Node.js) 实现JavaScript在算法题中通常指Node.js环境使用ES6语法可以让代码更现代。function minRewards(scores) { if (!scores || scores.length 0) { return 0; } const n scores.length; if (n 1) { return 1; } const rewards new Array(n).fill(1); // 使用fill方法初始化 // 从左到右 for (let i 1; i n; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左 for (let i n - 2; i 0; i--) { if (scores[i] scores[i 1]) { // 注意这里需要更新rewards[i]可能覆盖从左到右的结果 rewards[i] Math.max(rewards[i], rewards[i 1] 1); } } // 使用reduce求和函数式编程风格 const total rewards.reduce((sum, current) sum current, 0); return total; } // 测试 const scores1 [1, 3, 2, 1, 4, 2]; console.log(最少零食数: ${minRewards(scores1)}); // 输出 10 const scores2 [1, 2, 2]; console.log(最少零食数: ${minRewards(scores2)}); // 输出 4JavaScript实操要点数组初始化new Array(n).fill(1)是ES6中初始化固定值数组的推荐方式简洁高效。变量声明使用const声明不会改变的变量如n,rewards使用let声明循环变量i符合现代JS规范。求和使用数组的reduce方法求和是非常地道的函数式编程写法(sum, current) sum current, 0这个回调函数累加每个元素0是初始值。严格比较算法中比较分数用的是这没问题。在JS中如果比较可能涉及不同类型要特别注意和的区别但本题中都是数字用即可。5. 算法扩展思考与优化空间“零食奖励”的标准解法是两次遍历时间复杂度O(n)空间复杂度O(n)。这已经是这个问题的最优解法之一。但在面试或深入学习时我们还可以思考以下几个方向空间复杂度优化到O(1)理论上如果只求总数而不需要知道每个孩子的具体奖励数可能存在常数空间复杂度的解法。一种思路是寻找序列中的“波谷”分数比两边都低的孩子从波谷开始向两边爬坡分配。但实现起来比两次遍历复杂且容易出错。在机试或面试中清晰正确的O(n)空间解法远优于复杂且易错的O(1)空间尝试。如果规则变化怎么办比如规则变成“分数不低于邻居则零食数不低于邻居”即包含等于的情况。我们只需要把代码中的判断条件改为即可。但要注意这样可能会导致零食总数增加。这是一个很好的 follow-up 问题考察你是否真正理解算法逻辑。环形排列怎么办如果小朋友是围成一个圈坐的首尾相邻问题就变成了“环形分发糖果”。解决思路是将环形拆解在两次线性遍历后还需要处理首尾相接处的约束。这可以作为一道更难的进阶题目。6. 机试实战技巧与避坑指南结合这道“零食奖励”我总结了几点华为OD机试乃至大多数算法机试的通用技巧先理清思路再动手编码花5-10分钟在草稿纸上画一画走一遍样例。比如画出一排小朋友的分数手动模拟分配过程验证你的算法思路。切忌看到题目就立刻开始敲代码。重视边界条件空输入、单元素、全相等、严格递增、严格递减、V型序列……在脑子里过一遍这些特殊情况你的代码鲁棒性会大大提升。机试的测试用例一定会包含这些边界情况。选择熟悉的语言华为OD通常支持多种语言。选择你最熟悉、编码速度最快的那一门。不要为了“炫技”而使用生疏的语言。本题中Python在编码效率上优势明显。注意输入输出格式机试平台通常是标准输入输出。练习时就要习惯从sys.stdin(Python)、Scanner(Java)、cin(C)读取数据并按格式输出。务必先本地测试通过样例再提交。时间复杂度与空间复杂度即使题目不明确要求自己也应该清楚算法的时间复杂度。对于本题O(n)的时间复杂度和O(n)的空间复杂度是完全可接受的。如果遇到数据规模n达到10^5甚至更大O(n^2)的暴力解法一定会超时。调试与验证写完代码后用题目给的样例、自己设计的边界样例如空数组、[1]、[3,2,1]、[1,2,2,1]都跑一遍。在本地IDE里设置断点或者打印中间变量如每次遍历后的rewards数组是快速定位逻辑错误的好方法。回到“零食奖励”这道题它就像一面镜子照出的不仅是你的编码能力更是将模糊的业务需求转化为清晰、可执行逻辑的抽象能力。这种能力无论是在OD机试中还是在真实的软件开发中都至关重要。希望这篇详细的拆解能帮你吃透这一类问题。下次再遇到“发糖果”、“评奖金”、“接雨水”这类有着相似内核的题目时你就能一眼看穿本质快速找到解题的钥匙。
贪心算法实战：从“分发糖果”到华为OD“零食奖励”的多语言详解
发布时间：2026/7/12 9:29:42
1. 项目概述从“零食奖励”看华为OD机试的算法思维最近在帮几个准备冲刺华为OD机试的朋友做模拟训练发现一个挺有意思的现象很多同学一看到“动态规划”、“图论”这些词就头疼觉得是“硬骨头”反而对一些看似生活化的题目掉以轻心。比如这道“零食奖励”标题听起来人畜无害好像是个简单的分配问题但真上手一写各种边界条件和状态转移的逻辑陷阱就都冒出来了。这道题是2025C卷的新题它考察的核心远不止是写对一个循环或者判断而是对贪心策略的深刻理解和对问题本质的抽象能力。今天我就结合这道题把C、Java、Python、C语言和JS五种语言的实现思路和代码细节都掰开揉碎了讲一遍更重要的是分享一套面对这类“场景应用题”的通用拆解方法。无论你是正在备战OD还是想巩固算法基础相信这篇从实战出发的深度解析都能给你带来不一样的启发。2. 核心需求与问题抽象2.1 题目场景还原与核心诉求我们先抛开代码把题目用大白话翻译一下。想象一个班主任要奖励班上一排坐着的小朋友零食。每个小朋友有一个“表现分”。奖励规则是公平原则每个小朋友至少得到1份零食。激励原则如果某个小朋友的表现分比相邻的小朋友高那么他得到的零食必须比那个相邻的小朋友多。我们的目标是在满足以上两条规则的前提下计算出需要准备的零食总数最少是多少。这本质上是一个约束优化问题。约束是规则1和2优化目标是“总数最小”。规则1给了我们一个基础值每人至少1个规则2则引入了变量使得我们不能再简单地给每人发1个了事。2.2 问题抽象与算法定位为什么说这道题“坑”多因为它完美地模拟了实际开发中产品经理给的一个看似简单的业务需求背后却需要精巧的设计。首先我们需要把“一排小朋友”抽象成一个整数数组scores数组的每个元素就是对应位置小朋友的表现分。我们的输出是另一个等长的数组rewards表示每个小朋友分到的零食数并且要满足rewards[i] 1公平原则如果scores[i] scores[i-1]那么rewards[i] rewards[i-1]左邻激励如果scores[i] scores[i1]那么rewards[i] rewards[i1]右邻激励在满足以上所有条件的前提下sum(rewards)最小。看到“相邻比较”和“最小总数”有经验的同学应该能立刻联想到经典的“分发糖果”问题。没错“零食奖励”就是这道经典题目的一个变体或直接应用。其标准解法是两次遍历的贪心算法。注意这里最容易犯的第一个错误是试图“一遍遍历搞定”。因为一个小朋友的零食数同时受左右两边邻居的影响只从左到右扫一遍无法处理“右边比左边高”但左边值还未确定的情况。必须把左右影响拆开处理。算法核心思想把“比邻居高则零食多”这个约束拆解成两个独立的子问题左规则当scores[i] scores[i-1]时保证rewards[i] rewards[i-1]。右规则当scores[i] scores[i1]时保证rewards[i] rewards[i1]。为了让总数最小我们在满足每个规则时都采取“最小幅度增加”的策略即只比邻居多1个。最后对于每个位置i为了同时满足左规则和右规则他最终得到的零食数rewards[i]应该是分别满足左规则和右规则时计算出的两个值的最大值。这个“取最大值”的操作是保证两个约束同时被满足的关键。3. 算法思路详解与多语言实现框架3.1 标准两次遍历贪心算法拆解理解了核心思想我们来看具体的步骤这是写出健壮代码的蓝图初始化创建一个长度与scores相同的数组rewards将所有元素初始化为1。这满足了“每人至少1个”的基础约束。第一次遍历从左到右处理“左规则”。从下标i 1开始遍历到数组末尾。如果scores[i] scores[i-1]那么为了满足左规则rewards[i]至少要比rewards[i-1]多1。我们采取最小化策略令rewards[i] rewards[i-1] 1。经过这次遍历我们确保了对于任何位置只要他比左边的邻居表现好他的零食数就一定比左边多。但此时还没有考虑右边邻居的影响。第二次遍历从右到左处理“右规则”。从下标i n-2开始倒数第二个遍历到数组开头i 0。如果scores[i] scores[i1]那么为了满足右规则rewards[i]至少要比rewards[i1]多1。同样我们取最小增量rewards[i] max(rewards[i], rewards[i1] 1)。这里为什么要用max因为rewards[i]在第一次遍历后可能已经有了一个值比如它比左边高这个值可能已经大于rewards[i1] 1。我们取两者中的较大者才能同时满足左规则如果存在和当前的右规则。计算结果遍历rewards数组求和即为所需的最少零食总数。这个算法的时间复杂度是 O(n)空间复杂度是 O(n)用于存储rewards数组。3.2 关键边界与陷阱分析在动手写代码前必须想清楚以下几个边界情况它们往往是测试用例的重点也是面试时考察你思维严密性的地方空数组或单元素数组如果小朋友人数为0总数应该是0。如果只有1个小朋友根据规则他至少得1个总数就是1。代码中需要对输入长度进行判断。分数相等的情况规则只说了“高于”才需要更多零食。如果分数相等是没有强制要求的。因此在两次遍历的判断条件中必须是严格大于而不是大于等于。这是很多同学容易忽略的细节。非严格递增/递减序列比如分数是[1, 2, 2, 3]。对于第一个2它比左边的1大所以rewards[1]变成2。第二个2它不比左边的2大所以rewards[2]保持为1。在从右向左遍历时第二个2比右边的3小所以规则不触发。最终第二个2的小朋友只得到1个零食而第一个2得到2个这是符合规则的分数相同零食数可以不同。这个例子很好地体现了算法的正确性。V型序列比如[1, 3, 2]。从左到右后rewards为[1, 2, 1]。从右到左时发现scores[1] (3) scores[2] (2)所以rewards[1]需要至少是rewards[2]12当前值已经是2满足。最终rewards[1]为2正确。4. 多语言代码实现与细节剖析接下来我们分别用五种语言实现上述算法。我会重点指出每种语言在实现时需要注意的语法特性和性能细节。4.1 C 实现C的实现需要关注容器选择、循环边界和标准库函数的使用。#include iostream #include vector #include algorithm // 用于max函数 #include numeric // 用于accumulate求和 using namespace std; int minRewards(vectorint scores) { int n scores.size(); if (n 0) return 0; if (n 1) return 1; vectorint rewards(n, 1); // 初始化每人至少1个 // 从左到右遍历满足左规则 for (int i 1; i n; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左遍历满足右规则并取最大值 for (int i n - 2; i 0; --i) { if (scores[i] scores[i 1]) { // 关键取当前值和满足右规则所需值的较大者 rewards[i] max(rewards[i], rewards[i 1] 1); } } // 计算总和 int total accumulate(rewards.begin(), rewards.end(), 0); return total; } int main() { // 示例测试 vectorint scores1 {1, 3, 2, 1, 4, 2}; // 可以自己计算验证 cout 最少零食数: minRewards(scores1) endl; vectorint scores2 {1, 2, 2}; // 相等分数测试 cout 最少零食数: minRewards(scores2) endl; return 0; }C实操要点容器选择使用vectorint是最通用和高效的选择。避免使用原生数组除非有极致的性能要求且长度固定。求和操作使用numeric中的std::accumulate是标准且安全的求和方式比手写循环更清晰。第三个参数0是求和的初始值也决定了返回类型int。循环变量使用前缀i而非后缀i对于内置类型虽然性能差异可忽略但这是一个良好的习惯尤其在涉及迭代器的泛型代码中。max函数直接使用std::max清晰明了。4.2 Java 实现Java的实现要注意数组操作、循环以及使用Math.max。public class SnackRewards { public static int minRewards(int[] scores) { if (scores null || scores.length 0) { return 0; } int n scores.length; if (n 1) { return 1; } int[] rewards new int[n]; // 初始化 for (int i 0; i n; i) { rewards[i] 1; } // 从左到右 for (int i 1; i n; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左 for (int i n - 2; i 0; i--) { if (scores[i] scores[i 1]) { rewards[i] Math.max(rewards[i], rewards[i 1] 1); } } // 求和 int total 0; for (int reward : rewards) { total reward; } return total; } public static void main(String[] args) { int[] scores1 {1, 3, 2, 1, 4, 2}; System.out.println(最少零食数: minRewards(scores1)); // 输出应为 10 int[] scores2 {1, 2, 2}; System.out.println(最少零食数: minRewards(scores2)); // 输出应为 4 } }Java实操要点空值判断Java中方法参数可能是null所以优先进行if (scores null)判断这是健壮性编程的基本要求。数组初始化int[] rewards new int[n];并不会自动初始化为1必须显式循环赋值。也可以使用Arrays.fill(rewards, 1)但手写循环更直观且性能无差异。求和Java中没有内置的数组求和工具方法除非用Stream但小题大做手写循环求和是最直接的方式。Math.max使用Math.max进行两者取大。4.3 Python 实现Python的代码非常简洁利用列表推导式和内置函数可以写得非常优雅。def min_rewards(scores): if not scores: return 0 n len(scores) if n 1: return 1 rewards [1] * n # 优雅的初始化 # 从左到右遍历 for i in range(1, n): if scores[i] scores[i - 1]: rewards[i] rewards[i - 1] 1 # 从右到左遍历 for i in range(n - 2, -1, -1): # 注意range的用法起点终点不含步长 if scores[i] scores[i 1]: # 使用max函数取较大值 rewards[i] max(rewards[i], rewards[i 1] 1) return sum(rewards) # 内置sum函数非常方便 # 测试 if __name__ __main__: scores1 [1, 3, 2, 1, 4, 2] print(f最少零食数: {min_rewards(scores1)}) # 输出 10 scores2 [1, 2, 2] print(f最少零食数: {min_rewards(scores2)}) # 输出 4Python实操要点列表初始化[1] * n是创建包含n个1的列表的最高效方式清晰且快速。反向遍历range(n-2, -1, -1)是经典的反向循环写法。起点是n-2倒数第二个索引终点是-1意味着要包含0步长为-1。也可以使用reversed(range(n-1))但不如直接指定range直观。求和sum(rewards)是Python的内置函数直接对可迭代对象求和代码简洁高效。条件判断if not scores:可以同时判断None和空列表是Pythonic的写法。4.4 C语言实现C语言的实现需要手动管理内存本例中不需要动态分配和循环更接近底层。#include stdio.h #include stdlib.h // 为了使用动态内存分配如果输入大小不定 // 假设scores数组和长度n已知rewards数组已分配好空间 int minRewards(int* scores, int scoresSize) { if (scoresSize 0) return 0; if (scoresSize 1) return 1; // 在栈上分配奖励数组如果数据量大可考虑动态分配 int* rewards (int*)malloc(scoresSize * sizeof(int)); if (rewards NULL) { return -1; // 分配失败返回错误码 } // 初始化 for (int i 0; i scoresSize; i) { rewards[i] 1; } // 从左到右 for (int i 1; i scoresSize; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左 for (int i scoresSize - 2; i 0; i--) { if (scores[i] scores[i 1]) { int newReward rewards[i 1] 1; rewards[i] (rewards[i] newReward) ? rewards[i] : newReward; // 三目运算符实现max } } // 求和 int total 0; for (int i 0; i scoresSize; i) { total rewards[i]; } free(rewards); // 释放动态分配的内存 return total; } int main() { int scores1[] {1, 3, 2, 1, 4, 2}; int size1 sizeof(scores1) / sizeof(scores1[0]); printf(最少零食数: %d\n, minRewards(scores1, size1)); int scores2[] {1, 2, 2}; int size2 sizeof(scores2) / sizeof(scores2[0]); printf(最少零食数: %d\n, minRewards(scores2, size2)); return 0; }C语言实操要点内存管理示例中使用了malloc动态分配rewards数组务必记得在函数返回前free否则会造成内存泄漏。这是C语言编程的核心纪律之一。数组长度传递C语言中数组作为参数会退化为指针必须同时传递数组长度scoresSize。max函数C标准库没有内置的max函数用于整型通常需要自己定义宏或者像示例中一样使用三目运算符(a b) ? a : b。错误处理malloc可能失败返回NULL。生产代码中必须检查并处理这种错误示例中简单返回了-1。4.5 JavaScript (Node.js) 实现JavaScript在算法题中通常指Node.js环境使用ES6语法可以让代码更现代。function minRewards(scores) { if (!scores || scores.length 0) { return 0; } const n scores.length; if (n 1) { return 1; } const rewards new Array(n).fill(1); // 使用fill方法初始化 // 从左到右 for (let i 1; i n; i) { if (scores[i] scores[i - 1]) { rewards[i] rewards[i - 1] 1; } } // 从右到左 for (let i n - 2; i 0; i--) { if (scores[i] scores[i 1]) { // 注意这里需要更新rewards[i]可能覆盖从左到右的结果 rewards[i] Math.max(rewards[i], rewards[i 1] 1); } } // 使用reduce求和函数式编程风格 const total rewards.reduce((sum, current) sum current, 0); return total; } // 测试 const scores1 [1, 3, 2, 1, 4, 2]; console.log(最少零食数: ${minRewards(scores1)}); // 输出 10 const scores2 [1, 2, 2]; console.log(最少零食数: ${minRewards(scores2)}); // 输出 4JavaScript实操要点数组初始化new Array(n).fill(1)是ES6中初始化固定值数组的推荐方式简洁高效。变量声明使用const声明不会改变的变量如n,rewards使用let声明循环变量i符合现代JS规范。求和使用数组的reduce方法求和是非常地道的函数式编程写法(sum, current) sum current, 0这个回调函数累加每个元素0是初始值。严格比较算法中比较分数用的是这没问题。在JS中如果比较可能涉及不同类型要特别注意和的区别但本题中都是数字用即可。5. 算法扩展思考与优化空间“零食奖励”的标准解法是两次遍历时间复杂度O(n)空间复杂度O(n)。这已经是这个问题的最优解法之一。但在面试或深入学习时我们还可以思考以下几个方向空间复杂度优化到O(1)理论上如果只求总数而不需要知道每个孩子的具体奖励数可能存在常数空间复杂度的解法。一种思路是寻找序列中的“波谷”分数比两边都低的孩子从波谷开始向两边爬坡分配。但实现起来比两次遍历复杂且容易出错。在机试或面试中清晰正确的O(n)空间解法远优于复杂且易错的O(1)空间尝试。如果规则变化怎么办比如规则变成“分数不低于邻居则零食数不低于邻居”即包含等于的情况。我们只需要把代码中的判断条件改为即可。但要注意这样可能会导致零食总数增加。这是一个很好的 follow-up 问题考察你是否真正理解算法逻辑。环形排列怎么办如果小朋友是围成一个圈坐的首尾相邻问题就变成了“环形分发糖果”。解决思路是将环形拆解在两次线性遍历后还需要处理首尾相接处的约束。这可以作为一道更难的进阶题目。6. 机试实战技巧与避坑指南结合这道“零食奖励”我总结了几点华为OD机试乃至大多数算法机试的通用技巧先理清思路再动手编码花5-10分钟在草稿纸上画一画走一遍样例。比如画出一排小朋友的分数手动模拟分配过程验证你的算法思路。切忌看到题目就立刻开始敲代码。重视边界条件空输入、单元素、全相等、严格递增、严格递减、V型序列……在脑子里过一遍这些特殊情况你的代码鲁棒性会大大提升。机试的测试用例一定会包含这些边界情况。选择熟悉的语言华为OD通常支持多种语言。选择你最熟悉、编码速度最快的那一门。不要为了“炫技”而使用生疏的语言。本题中Python在编码效率上优势明显。注意输入输出格式机试平台通常是标准输入输出。练习时就要习惯从sys.stdin(Python)、Scanner(Java)、cin(C)读取数据并按格式输出。务必先本地测试通过样例再提交。时间复杂度与空间复杂度即使题目不明确要求自己也应该清楚算法的时间复杂度。对于本题O(n)的时间复杂度和O(n)的空间复杂度是完全可接受的。如果遇到数据规模n达到10^5甚至更大O(n^2)的暴力解法一定会超时。调试与验证写完代码后用题目给的样例、自己设计的边界样例如空数组、[1]、[3,2,1]、[1,2,2,1]都跑一遍。在本地IDE里设置断点或者打印中间变量如每次遍历后的rewards数组是快速定位逻辑错误的好方法。回到“零食奖励”这道题它就像一面镜子照出的不仅是你的编码能力更是将模糊的业务需求转化为清晰、可执行逻辑的抽象能力。这种能力无论是在OD机试中还是在真实的软件开发中都至关重要。希望这篇详细的拆解能帮你吃透这一类问题。下次再遇到“发糖果”、“评奖金”、“接雨水”这类有着相似内核的题目时你就能一眼看穿本质快速找到解题的钥匙。
相关文章
从COCI竞赛题解析C++算法：序列冲突消除与贪心BFS实战
1. 项目概述：从一道COCI竞赛题看C算法实战 最近在带学生刷信奥（信息学奥林匹克）题目时，又遇到了这道经典的P7935，它来自COCI 2007/2008赛季的第五题，题目名叫“AVOGADRO”。很多刚接触算法竞赛的同学&#…
Scan Context 与 Scan Context++ 对比评测：3大改进点与回环检测 F1-score 提升分析
Scan Context 与 Scan Context 深度对比：技术演进与性能突破激光SLAM领域的回环检测技术近年来取得了显著进展，其中Scan Context系列算法因其独特的极坐标描述子和高效的两阶段匹配策略，成为工业界和学术界广泛采用的解决方案。本文将深入剖析…
Zeta 变换器电路
一、拓扑基础定位Zeta 变换器是同极性升降压 DC-DC 拓扑，与 SEPIC 互为对偶电路，和 Cuk 电路同属四阶 LC 升降压架构。 核心特征：输入、输出电压极性完全相同；输入电流断续，输出电流连续（与 SEPIC 恰好相反…
HiP-AD：多粒度可变形注意力驱动的自动驾驶可解释规划架构
1. HiP-AD不是又一个“端到端”概念包装，而是把“规划”从黑箱里拽出来重装了HiP-AD这个标题里藏着三个被行业反复咀嚼却始终没嚼透的词：端到端、多粒度、可变形注意力。很多人第一眼扫过去，会觉得这又是某家公司在顶会刷存在感的常规操作——…
基于TB6593FNG与PIC18的直流电机精密控制系统设计
1. 项目背景与核心目标在工业自动化和小型机电设备开发领域，直流电机控制一直是核心技术难点。传统方案往往面临驱动效率低、控制精度差、系统稳定性不足等问题。本项目采用东芝TB6593FNG驱动芯片与Microchip PIC18LF4553微控制器组合，构建了一套高性能直…
基于MA12070和STM32F765ZI的高保真音频系统设计
1. 项目概述：构建基于MA12070和STM32F765ZI的高保真音频系统在数字音频处理领域，如何平衡功率效率与音质表现一直是工程师面临的挑战。MA12070作为英飞凌推出的高效D类音频放大器IC，与STM32F765ZI高性能MCU的组合，为解决这一问题提…
人形机器人关节模组：高集成机电系统设计与实操要点
1. 项目概述：人形机器人关节模组不是“拼装玩具”，而是整机运动能力的物理锚点人形机器人关节模组，这个词最近频繁出现在技术论坛、供应链会议和高校实验室白板上。它不是传统工业机械臂里那个标着型号、贴着标签的“减速器电机”组合件&…
遗传算法工程化实战：选择机制、交叉算子与变异率的动态平衡
1. 项目概述：为什么第二部分比第一部分更值得细读“遗传算法入门——第二部分”这个标题看似平平无奇，甚至带点教科书式的枯燥感，但如果你已经看过第一部分，或者自己动手写过一个最简版的遗传算法（比如用Python跑通了“…
终极Windows游戏控制器模拟指南：5分钟让任何设备变身专业手柄
终极Windows游戏控制器模拟指南：5分钟让任何设备变身专业手柄 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus 你是否曾因为游戏只支持特定手柄而…
MQ-2 烟雾传感器 ESP32-S3 驱动实战：ADC 读取与阈值校准 3 步完成
MQ-2 烟雾传感器 ESP32-S3 驱动实战：ADC 读取与阈值校准 3 步完成在智能家居和工业安全监测领域，烟雾检测是一个至关重要的环节。MQ-2 作为一款高性价比的半导体烟雾传感器，因其对多种可燃气体（如液化气、丙烷、氢气等）…
SPEC CPU 2006 v1.0.1 基准测试实战：ARM/X86/MIPS 三平台配置与 3 轮测试结果解读
SPEC CPU 2006 跨平台基准测试深度实战：ARM/X86/MIPS 架构配置优化与结果分析方法论在当今多元化的计算架构时代，如何客观评估不同处理器平台的真实性能成为系统工程师和性能优化专家的核心挑战。SPEC CPU 2006 作为业界公认的计算密集型基准测试套件&am…
每天60s读懂世界：2026年7月11日重点要闻解读
🔥 个人主页：杨利杰YJlio❄️ 个人专栏：《Windows 疑难杂症与工单复盘案例库》 《Sysinternals实战教程》《WINDOWS教程》 《Windows PowerShell 实战》 《人工智能实战合集》《超简单：用Python让Excel飞起来》🌟…
MQ-2 烟雾传感器 ESP32-S3 驱动实战：ADC 读取与阈值校准 3 步完成
MQ-2 烟雾传感器 ESP32-S3 驱动实战：ADC 读取与阈值校准 3 步完成在智能家居和工业安全监测领域，烟雾检测是一个至关重要的环节。MQ-2 作为一款高性价比的半导体烟雾传感器，因其对多种可燃气体（如液化气、丙烷、氢气等）…
SPEC CPU 2006 v1.0.1 基准测试实战：ARM/X86/MIPS 三平台配置与 3 轮测试结果解读
SPEC CPU 2006 跨平台基准测试深度实战：ARM/X86/MIPS 架构配置优化与结果分析方法论在当今多元化的计算架构时代，如何客观评估不同处理器平台的真实性能成为系统工程师和性能优化专家的核心挑战。SPEC CPU 2006 作为业界公认的计算密集型基准测试套件&am…
每天60s读懂世界：2026年7月11日重点要闻解读
🔥 个人主页：杨利杰YJlio❄️ 个人专栏：《Windows 疑难杂症与工单复盘案例库》 《Sysinternals实战教程》《WINDOWS教程》 《Windows PowerShell 实战》 《人工智能实战合集》《超简单：用Python让Excel飞起来》🌟…
FAE放射组学分析工具：医学影像特征探索的完整解决方案
FAE放射组学分析工具：医学影像特征探索的完整解决方案 【免费下载链接】FAE FeAture Explorer 项目地址: https://gitcode.com/gh_mirrors/fae/FAE 你是否曾经面对海量医学影像数据感到无从下手？想要从CT、MRI等影像中提取有价值的定量特征&#…
0.69B参数实现中文多模态AI：揭秘Qwen3-SmVL模型融合技术的完整实战指南
0.69B参数实现中文多模态AI：揭秘Qwen3-SmVL模型融合技术的完整实战指南 【免费下载链接】happy-llm 📚 从零开始构建大模型 项目地址: https://gitcode.com/GitHub_Trending/ha/happy-llm 还在为大型多模态模型动辄数十亿参数、显存占用高而烦恼&…
解锁AMD Ryzen处理器性能潜力的SMU调试神器：从新手到专家的完整指南
解锁AMD Ryzen处理器性能潜力的SMU调试神器：从新手到专家的完整指南 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址…