LeetCode 962. 最大宽度坡

约 4 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
数组 双指针 栈 单调栈

题目描述

✅ 962. 最大宽度坡

image-20260929105428621

题意分析

找到两个下标 i < j，满足 nums[i] <= nums[j]，并最大化宽度 j - i。只限制两个端点的值，中间元素的大小不影响是否合法。不存在这样的下标对时返回 0。

解法：候选单调栈 + 反向扫描

核心思路

[!blue]

先筛选可能成为最优左端的位置。若在位置 i 之前已经存在 p，满足 nums[p] <= nums[i]，那么任何能与 i 配对的右端也能与 p 配对，而且 p 更早、宽度更大。因此 i 可以舍弃，只有新的前缀最小值需要保留。

从左向右把这些下标压栈，栈内下标递增，对应数值严格递减。遇到相等值也不入栈，因为更早的同值位置一定更有利。栈顶因此是剩余候选中值最小的一个。

再从右向左枚举右端 j。若 nums[j] >= nums[栈顶]，当前 j 就是这个候选能遇到的最右匹配位置，计算宽度后可以永久弹出；今后的右端只会更靠左，不可能让这个候选取得更大宽度。

同一个右端可能让多个候选达到各自最大宽度，因此要持续弹栈。若栈顶都不能匹配，栈中更早候选的值更大，也都不能匹配当前右端，可以直接换下一个 j。这样既保留了所有可能最优的左端，又为每个候选找到最远右端。

解题步骤

  1. 正向扫描数组；栈为空，或当前值严格小于栈顶值时，将当前下标入栈。
  2. 将答案初始化为 0，从末尾向前枚举 j。
  3. 只要栈非空且栈顶值不大于 nums[j]，就用 j - 栈顶下标 更新答案，并弹出这个候选。
  4. 处理完所有右端后返回最大宽度。

若某候选在右侧没有合法伙伴，它最迟会在扫描到自身时以宽度 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)$。两次扫描各经过数组一次；内层虽然使用循环，但每个下标至多入栈和出栈一次，弹栈总次数也是线性的。
  • 空间复杂度：$O(n)$，严格递减数组会使所有下标都成为候选。

关键点总结

[!green]

  • 更早且值不大的位置，在所有可能右端下都优于较晚位置，因此只保留前缀新最小值。
  • 从右向左扫描，使候选首次匹配时就能确定它的最大宽度。
  • 栈顶值最小；它都不满足时，栈内其余候选也不满足当前右端。

易错点总结

[!yellow]

  • 栈必须存下标，单独存值无法计算宽度。
  • 不能正向扫描右端后立即弹出候选，那时未来还可能出现更远的匹配。
  • 内层只弹一个候选，会漏掉同一右端对其他候选提供的最远匹配。
  • 匹配允许值相等，条件必须包含等号。
  • 宽度是 j - i，不是包含两端的元素个数 j - i + 1。

相似题目

题目 难度 关联与区别
1124. 表现良好的最长时间段 中等 同样先保存单调下降的左端候选，再从右向左匹配以最大化下标差，比较条件有所不同。
121. 买卖股票的最佳时机 简单 同样只允许左位置早于右位置，但本题最大化距离而非数值差，需要保留合适的左端候选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/74003159
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！