尧图网站建设 
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[i1], ..., 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-11) 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-01) 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.mdEvery 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确保所有元素在遍历结束时都能出栈参与计算。完整代码与逐行解读语言支持Pythonclass 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逐行解读nums [0]追加哨兵元素保证栈在遍历结束后被清空。由于nums[i] 10一定小于所有元素能触发全部剩余元素的弹出。while st and nums[st[-1]] nums[i]当栈顶元素严格大于当前元素时说明当前索引i就是栈顶元素的下一个更小位置。这里使用严格大于保证求的是严格更小的位置与左右开区间的计数方式匹配。left st[-2] if len(st) 1 else -1栈顶元素st[-1]左侧第一个严格更小的位置是它左侧相邻的栈内元素st[-2]若栈中只有这一个元素则左侧边界取-1虚拟边界。也可以先st.pop()再取新的st[-1]二者等价。if left k i判断下标k是否落在开区间(left, i)内。由于left和i都是不可取到的边界这里不能有等号。只有当k在区间内时才能构造出包含k且最小值为nums[st[-1]]的好子数组。ans max(ans, (i - left - 1) * nums[st[-1]])(i - left - 1)是开区间(left, i)内所有子数组的数量乘以最小值nums[st[-1]]即得到以该元素为最小值的最大贡献更新答案。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) 的暴力枚举。延伸思考若去掉k的限制本题就退化为求所有子数组中最大分数即 problems/84.largest-rectangle-in-histogram.md 柱状图中最大矩形的变体最小值 × 宽度最大化去掉left k i判断即可。若nums中存在 0 或负数哨兵值就不能再用0需要改用小于所有元素的值如float(-inf)参见 problems/Every-Sublist-Min-Sum.md且扩张必然有利的前提也不再成立解法需要相应调整。关于相等元素的处理本题弹出条件用严格大于配合严格小于的边界定义保证每个最小值区间只被统计一次不会出现相等元素导致的重叠计数或边界歧义。总结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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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[i1], ..., 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-11) 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-01) 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.mdEvery 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确保所有元素在遍历结束时都能出栈参与计算。完整代码与逐行解读语言支持Pythonclass 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逐行解读nums [0]追加哨兵元素保证栈在遍历结束后被清空。由于nums[i] 10一定小于所有元素能触发全部剩余元素的弹出。while st and nums[st[-1]] nums[i]当栈顶元素严格大于当前元素时说明当前索引i就是栈顶元素的下一个更小位置。这里使用严格大于保证求的是严格更小的位置与左右开区间的计数方式匹配。left st[-2] if len(st) 1 else -1栈顶元素st[-1]左侧第一个严格更小的位置是它左侧相邻的栈内元素st[-2]若栈中只有这一个元素则左侧边界取-1虚拟边界。也可以先st.pop()再取新的st[-1]二者等价。if left k i判断下标k是否落在开区间(left, i)内。由于left和i都是不可取到的边界这里不能有等号。只有当k在区间内时才能构造出包含k且最小值为nums[st[-1]]的好子数组。ans max(ans, (i - left - 1) * nums[st[-1]])(i - left - 1)是开区间(left, i)内所有子数组的数量乘以最小值nums[st[-1]]即得到以该元素为最小值的最大贡献更新答案。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) 的暴力枚举。延伸思考若去掉k的限制本题就退化为求所有子数组中最大分数即 problems/84.largest-rectangle-in-histogram.md 柱状图中最大矩形的变体最小值 × 宽度最大化去掉left k i判断即可。若nums中存在 0 或负数哨兵值就不能再用0需要改用小于所有元素的值如float(-inf)参见 problems/Every-Sublist-Min-Sum.md且扩张必然有利的前提也不再成立解法需要相应调整。关于相等元素的处理本题弹出条件用严格大于配合严格小于的边界定义保证每个最小值区间只被统计一次不会出现相等元素导致的重叠计数或边界歧义。总结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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考