LeetCode 962. 最大宽度坡

2022-05-24 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 962. 最大宽度坡

题意分析

给一个整数数组 nums，「坡」定义为一对下标 (i, j) 满足 i < j 且 nums[i] <= nums[j]，它的宽度是 j - i。求最大宽度；如果不存在任何坡，返回 0。

读题要抓三点。第一，要最大化的是下标差而不是值差，值只用来当合法性约束，这一点决定了不能按值排序后直接取首尾。第二，条件是 nums[i] <= nums[j]，允许相等，所以 [1,1] 是宽度为 1 的合法坡。第三，「不存在则返回 0」——这个 0 也可以理解为 i = j 的退化情形，实现上把答案初始化为 0 即可自然覆盖，不必特判严格递减数组。

约束里 n 最大到 $5 \times 10^4$。这个规模是关键信号：$O(n^2)$ 的两两枚举约 25 亿次，必然超时；而 $O(n \log n)$ 或 $O(n)$ 都可以接受。同时元素值域也到 $5 \times 10^4$，值域不大但没小到能开桶直接做，所以突破口应该在下标结构而非值域。

再看一个隐含的性质：我们要的是最大宽度，这意味着对每个左端点，只关心它能配到的最右的合法右端点；反过来对每个右端点，只关心能配到的最左的合法左端点。任何「中间的」配对都不可能是答案，这条观察是后面所有剪枝的来源。

解法：单调递减栈 + 反向扫描

核心思路

暴力是双重循环枚举 (i, j)，检查 nums[i] <= nums[j] 并更新最大 j - i，复杂度 $O(n^2)$，n 到 5 万时超时。

瓶颈在于绝大多数左端点根本没有资格成为答案的左端。观察：若存在 i1 < i2 且 nums[i1] <= nums[i2]，那么 i2 作为左端点是完全多余的——任何能被 i2 配上的右端点 j（满足 nums[i2] <= nums[j]）必然也能被 i1 配上（因为 nums[i1] <= nums[i2] <= nums[j]），而 i1 更靠左，宽度 j - i1 > j - i2 严格更优。

于是有资格当左端点的下标必须满足：它的值严格小于它左边所有元素的值，也就是它是一个前缀最小值的新纪录。把这些下标从左到右收集起来，得到的序列下标递增、值严格递减——这就是那个单调栈。它的规模通常远小于 n，而且已经把「所有可能的最优左端点」一网打尽。

有了候选左端点栈，还要高效地为它们找最右的匹配。这里用从右往左扫描右端点 j：只要栈顶（即当前候选中值最大的那个左端点，也是下标最靠右的那个）满足 nums[j] >= nums[stack.top]，就用它更新答案并弹栈。

为什么弹栈是安全的？因为 j 是从右往左走的，当前这个 j 是栈顶元素能配到的最右位置——之后的 j 只会更小，宽度只会更窄，这个左端点再也贡献不了更优的答案，可以永久丢弃。

为什么可以只看栈顶而不必检查栈里更深的元素？栈从底到顶值严格递减，栈顶的值是最小的。如果栈顶都配不上（nums[j] < nums[stack.top]），那更深处值更大的元素就更配不上；反之栈顶配上并弹出后，新栈顶值更大，需要重新判断，所以这里用 while 而不是 if。

维持的不变量有两个：一是栈内下标递增且对应值严格递减，栈中保存的正是「尚未找到最右匹配的候选左端点」；二是每次弹栈时得到的 j - stack.top 就是该左端点能取到的最大宽度。两个不变量合起来保证扫描一遍就能求出全局最大值。

解题步骤

正向构建候选栈：i 从 0 到 n - 1，当栈为空或 nums[i] < nums[stack.top] 时把 i 入栈。为什么用严格小于：若 nums[i] 等于栈顶的值，那么 i 更靠右，作为左端点严格劣于栈顶，不必入栈；只有创造了新的前缀最小值才有资格。为什么下标 0 一定在栈里：它是第一个元素，没有左边的元素能压制它。

答案初始化为 0：对应「不存在坡」的情形，同时也让严格递减数组自然返回 0，不需要特判。

反向扫描右端点：j 从 n - 1 递减到 0。为什么必须从右往左：这样每个候选左端点第一次被匹配到时，对应的 j 就是它能取到的最右位置，弹栈才安全；若从左往右扫，第一次匹配到的是最左的 j，弹栈会把更优解丢掉。

while 循环弹栈更新：当栈非空且 nums[j] >= nums[stack.top] 时，用 j - stack.top 更新答案并弹栈。为什么条件带等号：题目允许 nums[i] == nums[j]。为什么用 while 不用 if：一个 j 可能同时是栈中多个候选左端点的最右匹配（栈顶弹出后新栈顶的值更大，仍可能不超过 nums[j]），必须一次性处理干净。

不必在外层提前退出：栈空之后内层 while 自然不执行，外层继续走完即可；也可以在栈空时 break，效果相同。

返回答案。

以 nums = [6, 0, 8, 2, 1, 5] 走一遍（预期答案 4）。
构建候选栈：i = 0，栈空，入栈，栈为 [0]（值 6）。i = 1，nums[1] = 0 < 6，入栈，栈为 [0, 1]（值 6, 0）。i = 2，nums[2] = 8，不小于栈顶值 0，跳过。i = 3、i = 4、i = 5 的值分别是 2、1、5，都不小于 0，全部跳过。最终栈为 [0, 1]，对应值 [6, 0]——只有下标 0 和 1 有资格当左端点，其余四个下标全被淘汰。
反向扫描：j = 5，nums[5] = 5 >= nums[stack.top] = nums[1] = 0，更新答案 5 - 1 = 4，弹出下标 1；新栈顶是下标 0，nums[0] = 6 > 5，不满足，内层结束。
j = 4，nums[4] = 1 < 6，不满足。j = 3，2 < 6，不满足。j = 2，nums[2] = 8 >= 6，更新答案 max(4, 2 - 0) = 4，弹出下标 0，栈空。
j = 1、j = 0 栈已空，无操作。返回 4，对应坡 (1, 5)：nums[1] = 0 <= nums[5] = 5，宽度 4。

再看一个全递减的用例 nums = [9, 8, 7]：候选栈会收下全部三个下标（值严格递减）；反向扫描时 j = 2 的值 7 小于栈顶 nums[2] = 7？注意栈顶此时正是下标 2 自己，7 >= 7 成立，更新答案 2 - 2 = 0 并弹栈；后续同理都只能得到 0。返回 0，符合「不存在坡」。这也说明为什么答案初值取 0 而不是 -1——退化配对天然给出 0。

代码实现

class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        int[] stack = new int[n];
        int top = -1;

        // 只有创造了新前缀最小值的下标，才有资格当左端点。
        for (int i = 0; i < n; i++) {
            if (top == -1 || nums[i] < nums[stack[top]]) {
                stack[++top] = i;
            }
        }

        int answer = 0;
        // 从右往左，保证第一次匹配到的就是该左端点的最右伙伴。
        for (int j = n - 1; j >= 0; j--) {
            while (top >= 0 && nums[j] >= nums[stack[top]]) {
                answer = Math.max(answer, j - stack[top]);
                top--;
            }
        }
        return answer;
    }
}

func maxWidthRamp(nums []int) int {
    n := len(nums)
    stack := make([]int, 0, n)
    // 只有创造了新前缀最小值的下标，才有资格当左端点。
    for i := 0; i < n; i++ {
        if len(stack) == 0 || nums[i] < nums[stack[len(stack)-1]] {
            stack = append(stack, i)
        }
    }

    answer := 0
    // 从右往左，保证第一次匹配到的就是该左端点的最右伙伴。
    for j := n - 1; j >= 0; j-- {
        for len(stack) > 0 && nums[j] >= nums[stack[len(stack)-1]] {
            i := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if j-i > answer {
                answer = j - i
            }
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$。凭什么：第一趟每个下标只做一次比较，至多入栈一次；第二趟外层走 n 个位置，内层的 while 每执行一次就永久弹出一个栈元素，而总入栈量不超过 n，因此内层累计执行次数不超过 n，两趟合计线性。

空间复杂度：$O(n)$。凭什么：候选栈最坏情况下（数组严格递减）会装下全部 n 个下标；除此之外只有几个标量，没有其他辅助结构。

关键点总结

要最大化下标差时，先问「哪些位置根本没资格当端点」。本题里被左边更小值压制的下标全部出局，候选集合从 $O(n)$ 个降到一条严格递减链，这是把 $O(n^2)$ 变成 $O(n)$ 的真正原因。

单调栈的用法有两类：一类是找「下一个更大/更小元素」，另一类就是本题这种「维护最优候选集合」。后者不做弹栈重建，只在构建时按单调性筛选，用途完全不同，别把两套模板搞混。

扫描方向的选择必须由「弹栈是否安全」倒推：从右往左扫才能保证首次匹配即最优匹配，从而一次性丢弃该候选。凡是用了「匹配后立刻丢弃」的贪心，都要先论证被丢弃的东西不可能更优。

构建候选栈用严格小于、匹配时用大于等于，两处的等号是刻意错开的：前者排除等值的靠右下标（劣解），后者接纳等值的右端点（题目允许）。等号放错会直接改变答案。

面试视角：先说 $O(n^2)$ 暴力，再说「左端点必须是前缀最小值」的淘汰论证，最后讲反向扫描为什么能弹栈。淘汰论证是这题的核心得分点，只写代码不解释会被认为是背模板。若面试官追问其他解法，可以提「按值排序下标后求最小前缀下标」的 $O(n \log n)$ 做法，或者二分答案配合前缀最小值/后缀最大值的写法，并说明本解更优。

「不存在则返回 0」这类要求常常可以用初值直接覆盖，退化配对 i = j 恰好给出 0，比写特判更稳。

易错点总结

错误写法：构建候选栈时用 nums[i] <= nums[stack.top] → 用例 [1,1,1] 中三个下标全部入栈，随后反向扫描能弹出全部，答案虽仍是 2 但栈里塞进了劣解；一旦数据换成 [3,3,0,3]，多余的等值下标会先被匹配走，答案从 3 变成 1。

错误写法：反向扫描的匹配条件写成 nums[j] > nums[stack.top] → 用例 [1,1] 中相等的一对不被承认，返回 0，而正确答案是 1。

错误写法：内层用 if 而不是 while → 用例 [6,0,8,2,1,5] 换成 [9,8,1,0,10] 时，j = 4 本应连续弹出多个候选，只弹一个会漏掉宽度更大的配对，答案偏小。

错误写法：从左往右扫描右端点并弹栈 → 用例 [6,0,8,2,1,5] 中下标 1 会在 j = 2 时就被弹出，得到宽度 1，而它真正的最优匹配在 j = 5，答案从 4 变成 2。

错误写法：只用一个指针从两端向中间收缩（套用盛水容器的双指针） → 用例 [6,0,8,2,1,5] 中收缩条件无法保证不漏解，因为这题的合法性由值的大小关系决定而非面积单调性，双指针的贪心前提不成立。

错误写法：候选栈保存值而不是下标 → 用例中弹栈时算不出 j - i，宽度信息丢失；单调栈存什么必须由答案的计算方式决定。

错误写法：答案初始化为 -1 或 Integer.MIN_VALUE → 用例 [9,8,7] 中不存在坡，返回负数而不是 0。

错误写法：忘记候选栈可能为空就访问栈顶 → 用例 [1,2,3] 中栈只有一个元素，j = 2 时弹空后继续访问 stack[top]，Java 里 top = -1 导致数组越界，Go 里切片索引 -1 直接 panic。

错误写法：先按值排序下标再取相邻差 → 用例 [6,0,8,2,1,5] 中排序后下标序列为 1,4,3,5,0,2，取相邻差得不到 4；正确的排序解法需要维护前缀最小下标，只取相邻差是错的。

错误写法：把「宽度」理解成 j - i + 1（元素个数） → 用例 [6,0,8,2,1,5] 返回 5 而不是 4，题目定义的宽度是下标差本身。

错误写法：构建候选栈时把 i = 0 漏掉（比如循环从 1 开始） → 用例 [0,5] 中唯一的合法左端点被跳过，返回 0，正确答案是 1。

相似题目

题目	难度	考察点
739. 每日温度	中等	单调栈的另一类用法：求下一个更大元素，弹栈时结算而非筛选候选
84. 柱状图中最大的矩形	困难	同样靠单调栈定位左右边界，但结算的是面积且需要哨兵处理收尾
42. 接雨水	困难	单调栈按层累加，也可用双指针；关注的是高度差而不是下标跨度
456. 132 模式	中等	也需从右往左维护单调栈并配合前缀最小值，是本题淘汰思路的进阶版
1124. 表现良好的最长时间段	中等	转成前缀和后求最大下标跨度，用的正是本题同款的单调栈加反向扫描
11. 盛最多水的容器	中等	同样最大化下标跨度，但目标函数带高度乘积，双指针收缩的贪心可以成立
581. 最短无序连续子数组	中等	靠前缀最大与后缀最小定位边界，是「单调性淘汰」思路的另一种落地