Leetcode 962

Link:

962. 最大宽度坡 - 给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。找出 A 中的坡的最大宽度，如果不存在，返回 0 。示例 1：输入：[6,0,8,2,1,5] 输出：4 解释：最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5. 示例 2：输入：[9,8,1,0,1,9,4,0,4,1] 输出：7 解释：最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1. 提示： 1. 2 <= A.length <= 50000 2. 0 <= A[i] <= 50000

https://leetcode.cn/problems/maximum-width-ramp

题目要求

给定整数数组nums，定义ramp为pair(i, j) 当且仅当 i ≤ j && nums[i] ≤ nums[j] 求nums中所有ramp的最大长度

核心算法和原理

从第一个元素开始遍历一遍，放到单调栈中。该单调栈满足：栈顶idx一定是从nums[0, i]中最小元素的下标

再反向遍历，对元素nums[j]，若其大于nums[st.top()]，则说明这是一个可行的ramp，计算width并与当前最大width进行比较更新，弹栈，重复判断直至栈空或者不大于nums[st.top]

为什么弹栈？为了尝试找到~~「以j为ramp.second的ramp中最小的ramp.first」~~「以st.top()为ramp.first的width最大的ramp」，反向遍历时第一个比nums[st.top()]大的元素即可以作为目标ramp.second

由于单调栈的性质，栈顶对应元素之前不存在比栈顶元素更小的元素，故这些解中的最优解即为max width

代码


class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        int ans = 0;
        int st[nums.size() + 1];
        int top = 1;
        st[1] = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[st[top]]) {
                st[++top] = i;
            } 
        }

        for (int j = nums.size() - 1; j >= 0 && top != 0; j--) {
            while (top != 0 && nums[st[top]] <= nums[j]) {
                ans = max(ans, j - st[top]);
                top--;
            }
        }
        return ans;
    }
};