第一次在在线判题系统里看到“贪吃的猴子”这五个字，我第一反应是：这莫不是个儿童故事？结果点进去才发现，它是一道正儿八经的算法题，而且第一直觉超级容易踩坑。题目本身不复杂：一排香蕉树，每棵树上挂着数量不等的香蕉，猴子每次只能从最左边或者最右边那一棵开吃，吃完整棵树再选择下一棵。给定香蕉树数组和一个采摘次数K，问你最多能吃到多少香蕉。很多同学包括我自己，刚看到这个题的第一秒就想用贪心，但真正认真推导后才发现，正确答案藏在一个非常刁钻的逆向思维里。这篇文章会把题目拆解、误区分析、滑动窗口解法、完整代码和边界处理一次性讲清楚，适合正在准备机试、笔试，或者想把“数组两端取数”这类题型吃透的朋友。
1. 猴子面前的一排香蕉树：题目描述与“贪心陷阱”
1.1 原题到底说了什么
先用最标准的语言把题目重新描述一遍：有一个长度为n的整数数组nums，nums[i]表示第i棵香蕉树上的香蕉数量。猴子一开始站在整排树的一端，每次操作只能选择当前最左边或最右边的一棵树，把整棵树上的香蕉全部摘走，并且这棵树就从序列中消失。猴子一共要执行恰好K次采摘，问在最优策略下最多能拿到多少根香蕉。
输入输出通常长这样：
4 2 5 1 4 2输出：
7解释一下：这里n=4，数组是[2, 5, 1, 4]，K=2。最优策略是第一次取左边的2，第二次取此时暴露出来的左边的5，一共拿到7根。如果你第一次贪心地取右边的4，第二次就只能取左边的2，一共只拿到6根。
再看一个更直观的例子：数组是[1, 2, 3, 4, 5, 6]，K=3。显然可以把右侧三棵6+5+4全拿走，结果是15。但你要是以为每次随便选哪边都一样，那就太小看这道题了。后面会详细说。
这类题目在笔试里经常出现，包装可能是拿卡牌、拿礼物、拿水果，核心模型完全一样：在数组两端取若干次，每次取一个元素，求累计和的最大值。
1.2 第一反应：每次都吃大的，结果翻车
我第一次做这道题时，脑子里冒出来的解法非常直接：既然每次只能取两端，那我每次比较一下左端和右端的香蕉数，谁多就取谁，这不就是最佳的贪心策略吗？感觉就像两个孩子抢一袋零食，每次都挑最大块的那个，按理说最后总量最多。
但这个直觉在这里是错的，而且错得很典型。
原因在于：你当前取走的一端会“揭开”它相邻的那棵树。如果旁边那棵树才是真正的大块头，你却为了另一端的几根香蕉放弃了它，后面再想拿就难了。换句话说，贪心策略只考虑了“这一口吃得多不多”，没考虑“这一口会不会挡住后面的好东西”。
这里的本质是：每次选择不仅影响当前收益，还影响下一次的可选范围。在只有左右两端可以选的情况下，选择左边意味着右边暂时不动，但同时把左边第二棵暴露出来；选择右边也是同理。局部最优无法推导出全局最优，因为整个解的空间是带顺序依赖的。
1.3 反例拆解：[2, 5, 1, 4]，K=2
我们拿一个短到不能再短的数组来验证贪心会挂。数组[2, 5, 1, 4]，K=2。
如果按“每次取较大端”的贪心策略操作：
- 初始两端是
2和4，4 > 2，取右边的4。剩余数组变成[2, 5, 1]。 - 此时两端是
2和1，2 > 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]，K=3。贪心先取左边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到Java
3.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 边界条件检查清单
做题最容易翻车的不是核心逻辑，而是边界条件。我把这道题能想到的边界情况整理成了清单，方便你自查：
| 场景 | 预期结果 | 说明 |
|---|---|---|
k=0 | 0 | 猴子一次都没吃 |
k=n | sum(nums) | 所有树都被吃光，留下空窗口 |
k>n | sum(nums) | 实际最多只能吃n棵，按全吃处理 |
n=0 | 0 | 没有树，题目一般不会出现，但最好兜底 |
| 数组元素为负数 | 仍然可以用逆向法 | 总和不一定是最大，但公式依然成立 |
| 数组元素巨大 | Java 使用long | 防止累加溢出 |
窗口长度L=0 | 直接返回total | 避免cur += nums[i] - nums[i]这类无意义更新 |
边界条件看似琐碎，但在线判题系统会自动构造各种刁钻数据。如果你提前知道这些坑，就能省下大量调试时间。
4. 提交过程中踩过的坑和这类题的变体
4.1 你可能会遇到的四个典型报错
第一个是超时。这是最常见的错误。如果你用递归枚举每一种取法，复杂度会随着K指数爆炸，哪怕K只有 30，也会慢到无法接受。如果你用朴素窗口枚举，每次重新求和，遇到n=10^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 性能实测与数据规模分析
我本地用n=100000、K=50000的随机数组测试了一下，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]。遍历K+1个可能起点后取最小值，答案依然是total - minWindow。这种写法在K很小、n很大的时候更直观，但需要O(n)的额外空间。
4.3 换个包装：LeetCode 1423 与后续扩展
“贪吃的猴子”这类题其实就是经典的“数组两端取数”模型。你在 LeetCode 上能找到一个几乎一模一样的题，叫1423. 可获得的最大点数：给一排卡牌，每张卡有分数，每次从开头或末尾拿一张，拿K张，问最多能拿多少分。解法一模一样，也是total - 最小剩余连续段和。
这个模型还能扩展到很多变体：
- 如果要求“必须左边连续取
x张，右边连续取K-x张”，那就直接用前缀和枚举所有可能的x，简单粗暴。 - 如果改成“每次可以取左端或右端的若干棵连续树，总共取
K次”，那就要变成区间 DP，复杂度会明显上升。 - 如果猴子不是只能从两端取，而是可以从任意位置开始取连续
K棵，那又会变成另一道最大子段和问题。
所以遇到题名很花哨的东西，先别被故事包装吓到。把题目翻译成算法语言，往往就是一个你练过很多遍的基础模型。
最后分享一个我自己的习惯：遇到左右两端取数的题，先在草稿纸上写一个两三个元素的反例，去验证“每次都取大端”是否真的最优。这个动作花不了三十秒，但能避免你在错误的道路上写几十行代码。真正值钱的是那一下从正向模拟到逆向窗口的转换，代码反而是最不重要的部分。搞清楚“剩下的连续子段和最小”这个点之后，你会发现“贪吃的猴子”这个名字，起得还挺贴切。
