962.maximum-width-ramp.md

962. 最大宽度坡

单减栈

遍历一遍，生成一个单调递减栈，保存从左到右出现的最小值的下标

从右到左，查找比当前单减栈栈顶元素大的第一个数，更新最大跨度

java

class Solution {
    public int maxWidthRamp(int[] nums) {

        if (nums.length <= 1) return 0;

        Stack<Integer> stk = new Stack<>();
        stk.add(0);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[stk.peek()]) stk.add(i);
        }

        int res = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            while (!stk.isEmpty() && nums[i] >= nums[stk.peek()]){
                res = Math.max(res, i - stk.peek());
                stk.pop();
            }
        }
        return res;
    }
}

javascript

var maxWidthRamp = function(A) {
    let stack = [], max = 0
    stack.push(0)
    for (let i = 1; i< A.length; i++){
        if (A[stack[stack.length-1]] > A[i]) stack.push(i)
    }

    // 从右到左查找比栈顶元素大的第一个数
    for(let i = A.length -1; i> = max; i--){
        while (stack.length > 0 && A[i] >= A[stack[stack.length-1]]){
            max = Math.max(i-stack.pop(), max)
        }
    }
    return max
};

单调栈分两类问题：

一种是从中间某一元素开始，求解此元素左右两边的最大或最小值 另一种求解整个序列，递增或递减子序列的最大跨度，此题为第二类

相似题目

1124. 表现良好的最长时间段