LeetCode 1793 好子数组的最大分数：贡献法与单调栈一次遍历解法详解

LeetCode 1793 好子数组的最大分数：贡献法与单调栈一次遍历解法详解

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文以 problems/1793.maximum-score-of-a-good-subarray.md 为核心，深入剖析 LeetCode 1793「好子数组的最大分数」的两种核心套路——贡献法（Contribution Technique）与单调栈（Monotonic Stack）。读完本文，你将掌握：如何把"枚举所有子数组"的暴力问题转化为"计算每个元素对答案的贡献"，如何用一次从左到右的单调栈遍历同时求出每个元素左右两侧第一个更小元素的位置，以及如何通过哨兵元素简化边界处理，最终在 O(N) 时间内通过数据规模达到 10^5 的测试用例。

题目回顾：好子数组的分数定义

题目描述

给你一个整数数组nums（下标从 0 开始）和一个整数k。

一个子数组(i, j)的分数定义为：

min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)

一个好子数组的两个端点下标需要满足：

i <= k <= j

请你返回好子数组的最大可能分数。

示例与约束

示例 1：

输入：nums = [1,4,3,7,4,5], k = 3 输出：15 解释：最优子数组的左右端点下标是 (1, 5)，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15

示例 2：

输入：nums = [5,5,4,5,4,1,1,1], k = 0 输出：20 解释：最优子数组的左右端点下标是 (0, 4)，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20

提示：

1 <= nums.length <= 10^5 1 <= nums[i] <= 2 * 10^4 0 <= k < nums.length

注意两个关键约束：数组长度可达 10^5，说明 O(N^2) 的暴力枚举必然超时；所有元素都大于 0，意味着子数组越长、分数在相同最小值下越大，"尽可能扩张"总是有利的。这两点直接决定了最优解法必须在线性时间内完成。

前置知识：单调栈

本题的推荐前置知识是单调栈。仓库中 thinkings/monotone-stack.md 对单调栈做了系统讲解：

单调栈是一种特殊的栈，要求栈中的元素是单调递增的或者单调递减的。单调栈适合的题目是求解"下一个大于 xxx"或者"下一个小于 xxx"这种题目。

从源码结构看，单调栈的核心性质是：当某个元素被弹出时，当前遍历到的元素就是它"下一个更小（更大）"的位置，而弹出后新的栈顶就是它"上一个更小（更大）"的位置。这个性质正是本题解法的基石。

仓库中还有一篇同思路的姊妹题 problems/Every-Sublist-Min-Sum.md（Every Sublist Min Sum），它同样使用"枚举每个元素作为最小值 + 单调栈求左右边界"的贡献法思路，可以直接对照学习。

核心思路一：贡献法（Contribution Technique）

把枚举子数组变成枚举最小值

这种"子数组分数 = 最小值 × 长度"的题目，基本套路都是贡献法——计算每一个元素对答案的贡献，累加即为答案。

如果不考虑k的限制，枚举每个元素nums[i]作为最小值，然后尽可能扩张（因为数组每一项都大于 0，扩张只会让长度变大、分数变大），扩张的前提是保证nums[i]仍然是这个子数组的最小值。

引入 k 的限制

考虑k之后，需要在"前一个更小下标"和"下一个更小下标"之间判断下标k是否落在其中。如果k不在区间内，则无法找到以nums[i]为最小值且下标满足条件的好子数组，跳过即可。

问题转化：求左右两侧严格更小的位置

问题进一步转化为：求nums[i]左右两侧严格小于nums[i]的元素的位置left和right。这样(left, right)内的所有子数组，nums[i]都是最小值（注意是开区间）。

• 以nums[i]为最小值的所有子数组个数为right - left - 1；
• 每个这样的子数组中nums[i]对答案的贡献都是nums[i]；
• 因此nums[i]对答案的总贡献为nums[i] * (right - left - 1)。

对所有i求和并取最大值，即得到最终答案。

这里对"严格小于"要格外注意：由于题目中分数取的是最小值，如果左右两侧存在与nums[i]相等的元素，那么以nums[i]为"唯一最小值"的子数组边界需要按代码中>（弹出栈顶）的写法处理，即右侧用严格更小、左侧也用严格更小来界定开区间，避免重复计数或漏算。

核心思路二：一次遍历的单调栈求左右边界

为什么是单调栈

求左右两侧严格小于的位置，让我们想到单调栈。不熟悉的话可以参考 thinkings/monotone-stack.md 中的专题讲解，套入模板即可。

一般的单调栈只求某一侧的严格小于位置，而本题要求左右两侧。容易想到的方案是：

• 从左向右遍历用一次单调栈，求每个位置i右侧第一个比它小的位置right；
• 再从右向左遍历用一次单调栈，求每个位置i左侧第一个比它小的位置left。

但原文档给出了更精妙的做法：用一个单调栈仅从左向右遍历一次即可同时完成。

一次遍历如何同时求出左侧更小位置

从左向右计算"右边第一个比它小"很容易（当前元素把栈顶弹出时，当前元素就是栈顶的下一个更小元素）。那么左侧第一个比它小的怎么求？

举个例子：比如 stack 目前是[0, 2, 3]（stack 中存的是索引）。那么对于 stack 中的3来说，前面严格小于它的就是 stack 中它左侧相邻的索引2。

这正是单调栈的单调性保证的：栈内元素按值严格递增（索引递增、值也递增），因此栈中相邻元素之间不存在比左边元素更小的夹层元素——若有，夹层元素早就把左边元素弹出了。于是栈中st[-1]左侧相邻的st[-2]就是nums[st[-1]]左侧第一个严格更小的位置。

哨兵元素：收尾清空栈

原文档代码中有一个容易被忽略的细节：

nums += [0]

由于所有nums[i] >= 1，在数组末尾追加一个0作为哨兵元素，可以保证在遍历结束时所有剩余元素都会被弹出并参与计算，避免栈中残留未处理的元素导致漏算。这是单调栈题目中非常常用的技巧，仓库 thinkings/monotone-stack.md 中将其总结为"哨兵法"：

对于上面的例子，我可以在原数组的右侧添加一个小于数组中最小值的项即可。这种技巧可以简化代码逻辑，大家尽量掌握。

同仓库的 problems/84.largest-rectangle-in-histogram.md 中也在 heights 首尾添加了两个哨兵元素，注释里明确说明了原因："末尾的哨兵就是为了将栈清空，防止遍历完成栈中还有没参与运算的数据"。

关键点总结

• 贡献法：将"枚举子数组"转化为"枚举最小值元素"，计算每个元素对答案的贡献并累加；
• 单调栈：一次从左向右的遍历，同时求出每个元素左右两侧第一个严格更小的位置；
• 开区间边界：left和right都是不可取到的边界，计数时长度为right - left - 1，判断k是否在区间内时不能使用等号；
• 哨兵元素：数组末尾追加0，确保所有元素在遍历结束时都能出栈参与计算。

完整代码与逐行解读

语言支持：Python

class Solution: def maximumScore(self, nums: List[int], k: int) -> int: # 单调栈求出 nums[i] 的下一个更小的下标 j st = [] ans = 0 nums += [0] for i in range(len(nums)): while st and nums[st[-1]] > nums[i]: # 含义：st[-1] 的下一个更小的是 i left = st[-2] if len(st) > 1 else -1 # 注意这里是 -2，因为 st[-1] 是当前元素，我们要在当前元素的左边记录找。也可以先 st.pop() 后在 st[-1] if left < k < i: # 注意由于 left 和 i 我们都无法取到（开区间），因此这里不能有等号 ans = max(ans, (i - left - 1) * nums[st[-1]]) st.pop() st.append(i) return ans

逐行解读

1. nums += [0]：追加哨兵元素，保证栈在遍历结束后被清空。由于nums[i] >= 1，0一定小于所有元素，能触发全部剩余元素的弹出。

2. while st and nums[st[-1]] > nums[i]：当栈顶元素严格大于当前元素时，说明当前索引i就是栈顶元素的下一个更小位置。这里使用严格大于>，保证求的是"严格更小"的位置，与"左右开区间"的计数方式匹配。

3. left = st[-2] if len(st) > 1 else -1：栈顶元素st[-1]左侧第一个严格更小的位置是它左侧相邻的栈内元素st[-2]；若栈中只有这一个元素，则左侧边界取-1（虚拟边界）。也可以先st.pop()再取新的st[-1]，二者等价。

4. if left < k < i：判断下标k是否落在开区间(left, i)内。由于left和i都是不可取到的边界，这里不能有等号。只有当k在区间内时，才能构造出包含k且最小值为nums[st[-1]]的好子数组。

5. ans = max(ans, (i - left - 1) * nums[st[-1]])：(i - left - 1)是开区间(left, i)内所有子数组的数量，乘以最小值nums[st[-1]]即得到以该元素为最小值的最大贡献，更新答案。

6. st.append(i)：当前索引入栈，维持栈的单调性。

与仓库模板的对照

对比 thinkings/monotone-stack.md 中的通用模板：

class Solution: def monostoneStack(self, arr: List[int]) -> List[int]: stack = [] ans = 定义一个长度和 arr 一样长的数组，并初始化为 -1 循环 i in arr: while stack and arr[i] > arr[栈顶元素]: peek = 弹出栈顶元素 ans[peek] = i - peek stack.append(i) return ans

可以看出本题代码就是模板的变形：弹出时机由"大于"改为"大于"，并在弹出时利用st[-2]同时拿到左侧边界，再叠加k的区间判断。仓库中 problems/84.largest-rectangle-in-histogram.md 的单调栈解法（ans = max(ans, heights[st.pop(-1)] * (i - st[-1] - 1))）与本题高度同构，只是少了k的约束；而 problems/Every-Sublist-Min-Sum.md 则展示了贡献法的另一种形态——每个被弹出的元素对答案的贡献为(i - last) * (last - left) * nums[last]，即"以该元素为最小值的子数组个数等于左侧可选起点数与右侧可选终点数的乘积"。建议三题对照学习，一次吃透贡献法 + 单调栈这一组合套路。

复杂度分析

• 时间复杂度：O(N)：数组只遍历一遍，每个元素最多入栈一次、出栈一次，因此整体为线性时间；
• 空间复杂度：O(N)：最坏情况下栈的长度与nums长度相同（例如数组单调递增时，所有元素都会依次入栈，直到末尾哨兵触发统一弹出）。

对于nums.length <= 10^5的数据规模，O(N) 的解法可以在毫秒级完成，远优于 O(N^2) 的暴力枚举。

延伸思考

1. 若去掉k的限制：本题就退化为求"所有子数组中最大分数"，即 problems/84.largest-rectangle-in-histogram.md 柱状图中最大矩形的变体（最小值 × 宽度最大化），去掉left < k < i判断即可。

2. 若nums中存在 0 或负数：哨兵值就不能再用0，需要改用小于所有元素的值（如float('-inf')，参见 problems/Every-Sublist-Min-Sum.md），且"扩张必然有利"的前提也不再成立，解法需要相应调整。

3. 关于相等元素的处理：本题弹出条件用严格大于>，配合"严格小于"的边界定义，保证每个"最小值区间"只被统计一次，不会出现相等元素导致的重叠计数或边界歧义。

总结

LeetCode 1793 是"贡献法 + 单调栈"这一经典组合的教科书级题目。核心脉络是：将"分数 = 最小值 × 长度"的枚举问题，转化为"枚举每个元素作为最小值，用单调栈 O(1) 求出左右边界，再结合 k 判断区间合法性"的线性问题。一次从左向右的遍历 + 末尾哨兵，即可在 O(N) 时间内优雅地解决 10^5 规模的输入。掌握本题后，你可以继续在仓库中刷 84. 柱状图中最大的矩形、Every Sublist Min Sum 等同源题目，并通过 thinkings/monotone-stack.md 巩固单调栈的通用模板与哨兵技巧。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode