↓Skip to main content
  1. Posts/

LeetCode-962 最大宽度坡

·1 min·
Table of Contents

LeetCode-962 最大宽度坡 #

Solution 1 #

对于 $j$ 左侧的 $i < k < j$ , 如果 $nums[i] <= nums[k]$ , 那么不用考虑 $k$ . 用一个栈来存储不断变小的 $nums[i]$ . 反向遍历 $j$ 来更新答案.

代码如下:

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        vector<int> s;
        int ans = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (s.empty() || nums[s.back()] > nums[i]) {
                s.push_back(i);
            }
        }

        int j = nums.size() - 1;
        while (!s.empty() && j >= 0) {
            while (j >= 0 && nums[j] < nums[s.back()]) {
                j--;
            }
            if (j >= 0) {
                ans = max(ans, j - s.back());
                s.pop_back();
            }
        }
        return ans;
    }
};

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        s, ans = [], 0
        for i, x in enumerate(nums):
            if s == [] or nums[s[-1]] > x:
                s.append(i)
        j = len(nums) - 1
        while s and j >= 0:
            while j >= 0 and nums[j] < nums[s[-1]]:
                j -= 1
            if j >= 0:
                ans = max(ans, j - s.pop())
        return ans