第一次在在线判题系统里看到“贪吃的猴子”这五个字我第一反应是这莫不是个儿童故事结果点进去才发现它是一道正儿八经的算法题而且第一直觉超级容易踩坑。题目本身不复杂一排香蕉树每棵树上挂着数量不等的香蕉猴子每次只能从最左边或者最右边那一棵开吃吃完整棵树再选择下一棵。给定香蕉树数组和一个采摘次数K问你最多能吃到多少香蕉。很多同学包括我自己刚看到这个题的第一秒就想用贪心但真正认真推导后才发现正确答案藏在一个非常刁钻的逆向思维里。这篇文章会把题目拆解、误区分析、滑动窗口解法、完整代码和边界处理一次性讲清楚适合正在准备机试、笔试或者想把“数组两端取数”这类题型吃透的朋友。1. 猴子面前的一排香蕉树题目描述与“贪心陷阱”1.1 原题到底说了什么先用最标准的语言把题目重新描述一遍有一个长度为n的整数数组numsnums[i]表示第i棵香蕉树上的香蕉数量。猴子一开始站在整排树的一端每次操作只能选择当前最左边或最右边的一棵树把整棵树上的香蕉全部摘走并且这棵树就从序列中消失。猴子一共要执行恰好K次采摘问在最优策略下最多能拿到多少根香蕉。输入输出通常长这样4 2 5 1 4 2输出7解释一下这里n4数组是[2, 5, 1, 4]K2。最优策略是第一次取左边的2第二次取此时暴露出来的左边的5一共拿到7根。如果你第一次贪心地取右边的4第二次就只能取左边的2一共只拿到6根。再看一个更直观的例子数组是[1, 2, 3, 4, 5, 6]K3。显然可以把右侧三棵654全拿走结果是15。但你要是以为每次随便选哪边都一样那就太小看这道题了。后面会详细说。这类题目在笔试里经常出现包装可能是拿卡牌、拿礼物、拿水果核心模型完全一样在数组两端取若干次每次取一个元素求累计和的最大值。1.2 第一反应每次都吃大的结果翻车我第一次做这道题时脑子里冒出来的解法非常直接既然每次只能取两端那我每次比较一下左端和右端的香蕉数谁多就取谁这不就是最佳的贪心策略吗感觉就像两个孩子抢一袋零食每次都挑最大块的那个按理说最后总量最多。但这个直觉在这里是错的而且错得很典型。原因在于你当前取走的一端会“揭开”它相邻的那棵树。如果旁边那棵树才是真正的大块头你却为了另一端的几根香蕉放弃了它后面再想拿就难了。换句话说贪心策略只考虑了“这一口吃得多不多”没考虑“这一口会不会挡住后面的好东西”。这里的本质是每次选择不仅影响当前收益还影响下一次的可选范围。在只有左右两端可以选的情况下选择左边意味着右边暂时不动但同时把左边第二棵暴露出来选择右边也是同理。局部最优无法推导出全局最优因为整个解的空间是带顺序依赖的。1.3 反例拆解[2, 5, 1, 4]K2我们拿一个短到不能再短的数组来验证贪心会挂。数组[2, 5, 1, 4]K2。如果按“每次取较大端”的贪心策略操作初始两端是2和44 2取右边的4。剩余数组变成[2, 5, 1]。此时两端是2和12 1取左边的2。两次共拿到4 2 6。如果采用最优策略先取左边的2。虽然这一步只拿了2但剩余数组变成[5, 1, 4]左边露出了一个大大的5。再取左边的5两次共拿到2 5 7。同样是两次操作结果从6变成7差距就在第一步的选择。贪心以为多拿2根是赚的结果丢了后面5和4中间更有价值的5。这个例子虽然数字很小但已经把“局部最优不等于全局最优”的道理展示得明明白白。如果你还想更明显一点可以构造[1, 100, 1, 1, 1, 1]K3。贪心先取左边1把100让出来后面虽然可以拿到100但你会额外少拿右端的机会。总之一旦遇到这种左右两端取数的题第一反应用贪心之前一定要先找反例否则很容易在笔试里丢掉整道题。2. 逆向思考吃掉的越多剩下的就越少2.1 一个关键观察剩下的香蕉永远是连续一串正面硬解这道题会非常痛苦。因为每一步都有两个选择如果你用递归去枚举所有路径复杂度是O(2^K)。哪怕K只有 30也会慢到怀疑人生。这时候需要换个角度想问题。猴子每次从最左端或最右端取走一棵树本质上是把原数组从两端往中间“剥皮”。无论它怎么取最终没有被取走的那部分香蕉树在原始数组中的位置一定是连续的。这一点可以这样理解数组的两端分别被往里推进左边取一次左边界往右移一格右边取一次右边界往左移一格。中间永远是一段完整的连续区间不会被跳过任何一棵树也不会被拆成两个不相邻的碎片。假设数组长度为n猴子要取K棵那么最后剩下的树的数量一定是n - K。也就是说不管猴子怎么左右横跳最后都会留下一个长度固定为L n - K的连续子数组。这个观察很关键。它把“从两端取”这样一个看起来非常动态的过程转换成了“选一个连续窗口留下来”的静态问题。2.2 把最大吃香蕉问题变成最小连续子段和问题有了上面的观察我们可以做一个简单的数学推导。设total表示所有香蕉的总数也就是sum(nums)。remain_sum表示最后没有被吃掉的连续子数组的香蕉总数。那么猴子最终吃到的香蕉数量就等于result total - remain_sumtotal是固定不变的。要让result最大唯一的办法就是让remain_sum最小。于是题目变成了在一个长度为n的数组中找到一个长度恰好为L n - K的连续子数组使得它的和最小。找到这个最小和之后用总和一减就是答案。这就是典型的“定长滑动窗口求最小和”问题也是一个你完全可以套模板的基础题。很多同学觉得它难是因为卡在了“正着模拟猴子的选择”上一旦反过来想整个思路瞬间豁然开朗。这里补充一个容易忽略的细节题目说的是“恰好取 K 次”所以我们留下的窗口长度必须严格等于n-K。如果题目改成“最多取 K 次”那就需要枚举 1 到 K 的所有情况取最大值那是另一个分支题目。做题之前一定要先确认到底是“恰好”还是“最多”一字之差解法完全不同。2.3 滑动窗口维护连续子段和寻找固定长度的连续子数组最小和最简单的暴力方法是枚举所有起点再对每个窗口重新求和。这样外层枚举起点O(n)内层求和O(L)总复杂度O(n*L)。在n和L都达到10^5的量级时这显然会超时。更好的做法是用滑动窗口维护窗口和。假设窗口长度为L我们先计算前L个元素的和cur记为初始窗口和。然后让窗口向右移动一位新窗口会多出一个右侧元素nums[i]同时丢弃一个左侧元素nums[i-L]。更新公式是cur cur nums[i] - nums[i - L]每次更新完把cur和当前记录的最小值min_remaining比较保留较小者。等窗口滑到数组结尾时min_remaining就是所有长度为L的连续子数组的最小和。为什么可以这样更新因为窗口整体平移内部的大部分元素没有变化只有新进来的一个元素和离开的一个元素发生了改变。用一个变量来记录窗口和比每次重新求整个窗口要高效得多。需要提醒的是滑动窗口求“和”并不需要单调队列、双端队列这些结构。那些结构是处理滑动窗口“最大值/最小值”时才需要的。这里只是因为窗口长度固定所以一个累积变量足够了。很多人在这一步绕了远路其实完全没必要。3. 完整代码实现与边界处理从Python到Java3.1 Python 版本三分钟跑通先把代码写完整可以直接复制到本地跑。这里用的是标准的滑动窗口写法from typing import List def max_bananas(nums: List[int], k: int) - int: n len(nums) # 如果采摘次数已经大于等于总数直接全吃 if k n: return sum(nums) # 如果一次都不摘结果为0 if k 0: return 0 total sum(nums) window_len n - k # 初始窗口前 window_len 个元素 cur sum(nums[:window_len]) min_remaining cur # 窗口从右往左滑实际上就是向右移动 for i in range(window_len, n): cur nums[i] - nums[i - window_len] if cur min_remaining: min_remaining cur return total - min_remaining对应主函数也一并给出方便在本地模拟输入输出if __name__ __main__: n int(input()) nums list(map(int, input().split())) k int(input()) print(max_bananas(nums, k))这里有几个细节值得注意k n时直接返回总和因为猴子最多只能摘n棵树。k 0时直接返回0。如果不做这两个特殊判断window_len n - k可能变成0甚至负数后面的滑动循环就会出现语义混乱。3.2 Java 版本注意类型和溢出Java 版本和 Python 版本思路完全一致但类型问题需要格外小心。很多人在笔试里用int存结果一旦数组元素很大总和直接溢出变成负数导致答案错误。import java.util.Scanner; public class GreedyMonkey { public static long maxBananas(int[] nums, int k) { int n nums.length; long total 0; for (int v : nums) { total v; } // 摘的次数超过总棵树全吃 if (k n) { return total; } // 一次都不摘 if (k 0) { return 0L; } int windowLen n - k; long cur 0; for (int i 0; i windowLen; i) { cur nums[i]; } long minRemaining cur; for (int i windowLen; i n; i) { cur nums[i] - nums[i - windowLen]; if (cur minRemaining) { minRemaining cur; } } return total - minRemaining; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] nums new int[n]; for (int i 0; i n; i) { nums[i] sc.nextInt(); } int k sc.nextInt(); System.out.println(maxBananas(nums, k)); } }Java 里long的最大值大约是9.22 * 10^18对于常见的n 10^5、nums[i] 10^9的数据总和最多10^14用long完全够用。如果不放心可以再想想题目是否给了更极端的约束必要时连long都不够就得用 Python 之类的语言。3.3 边界条件检查清单做题最容易翻车的不是核心逻辑而是边界条件。我把这道题能想到的边界情况整理成了清单方便你自查场景预期结果说明k00猴子一次都没吃knsum(nums)所有树都被吃光留下空窗口knsum(nums)实际最多只能吃n棵按全吃处理n00没有树题目一般不会出现但最好兜底数组元素为负数仍然可以用逆向法总和不一定是最大但公式依然成立数组元素巨大Java 使用long防止累加溢出窗口长度L0直接返回total避免cur nums[i] - nums[i]这类无意义更新边界条件看似琐碎但在线判题系统会自动构造各种刁钻数据。如果你提前知道这些坑就能省下大量调试时间。4. 提交过程中踩过的坑和这类题的变体4.1 你可能会遇到的四个典型报错第一个是超时。这是最常见的错误。如果你用递归枚举每一种取法复杂度会随着K指数爆炸哪怕K只有 30也会慢到无法接受。如果你用朴素窗口枚举每次重新求和遇到n10^5时同样会超时。解决办法就是滑动窗口一次遍历搞定。第二个是答案错误。如果你坚持使用“每次取较大端”的贪心策略会遇到我们前面提到的反例。即使你测试的几组数据都对了判题系统的隐藏数据也能把它打回原形。所以在提交之前先在草稿纸上验证一个反例能帮你省下大量提交次数。第三个是类型溢出。这个问题在 Java 里特别突出。有些同学看到nums[i]最大值只有10^5就觉得int够用但累加之后的总和可能超过2^31 - 1。一旦溢出不一定会立刻报错只是结果变成负数影响判断。建议 Java 代码里涉及累加和的地方全部用long。第四个是数组下标越界。常见发生在k和n的边界关系没有处理好的时候。比如window_len为0循环里用i - windowLen会出现i - 0 i虽然不越界但逻辑已经不对了。所以宁可多写几个if把特殊情况提前返回。4.2 性能实测与数据规模分析我本地用n100000、K50000的随机数组测试了一下Python 滑动窗口版本的运行时间大约在几十毫秒量级内存占用几乎是常量。换成朴素窗口枚举直接跑到天荒地老。不同方案的复杂度对比如下方案时间复杂度空间复杂度适用规模递归回溯O(2^K)O(K)仅适合K很小朴素窗口枚举O(n*L)O(1)几乎不实用滑动窗口求和O(n)O(1)最优前缀和 枚举起点O(n)O(n)也能过但空间略大如果你更喜欢前缀和写法也可以这样做先求出prefix[i]表示前i个元素的和然后枚举左侧取走的棵数left范围是0到K。对应的剩余窗口起点就是left窗口终点就是left L - 1窗口和等于prefix[left L] - prefix[left]。遍历K1个可能起点后取最小值答案依然是total - minWindow。这种写法在K很小、n很大的时候更直观但需要O(n)的额外空间。4.3 换个包装LeetCode 1423 与后续扩展“贪吃的猴子”这类题其实就是经典的“数组两端取数”模型。你在 LeetCode 上能找到一个几乎一模一样的题叫1423. 可获得的最大点数给一排卡牌每张卡有分数每次从开头或末尾拿一张拿K张问最多能拿多少分。解法一模一样也是total - 最小剩余连续段和。这个模型还能扩展到很多变体如果要求“必须左边连续取x张右边连续取K-x张”那就直接用前缀和枚举所有可能的x简单粗暴。如果改成“每次可以取左端或右端的若干棵连续树总共取K次”那就要变成区间 DP复杂度会明显上升。如果猴子不是只能从两端取而是可以从任意位置开始取连续K棵那又会变成另一道最大子段和问题。所以遇到题名很花哨的东西先别被故事包装吓到。把题目翻译成算法语言往往就是一个你练过很多遍的基础模型。最后分享一个我自己的习惯遇到左右两端取数的题先在草稿纸上写一个两三个元素的反例去验证“每次都取大端”是否真的最优。这个动作花不了三十秒但能避免你在错误的道路上写几十行代码。真正值钱的是那一下从正向模拟到逆向窗口的转换代码反而是最不重要的部分。搞清楚“剩下的连续子段和最小”这个点之后你会发现“贪吃的猴子”这个名字起得还挺贴切。