Medium

题目描述

数组中的坡是一对 (i, j)，其中 i < j 且 nums[i] <= nums[j]。这样的坡的宽度是 j - i。

给你一个整数数组 nums，返回 nums 中的最大宽度坡。如果不存在，则返回 0。

示例 1：

输入：nums = [6,0,8,2,1,5]
输出：4
解释：最大宽度坡出现在 (i, j) = (1, 5)：nums[1] = 0 且 nums[5] = 5。

示例 2：

输入：nums = [9,8,1,0,1,9,4,0,4,1]
输出：7
解释：最大宽度坡出现在 (i, j) = (2, 9)：nums[2] = 1 且 nums[9] = 1。

提示：

  • 2 <= nums.length <= 5 * 10^4
  • 0 <= nums[i] <= 5 * 10^4

解题思路

这个问题的核心是找到满足条件的最大宽度坡。我们需要找到索引对 (i, j)，使得 i < j 且 nums[i] <= nums[j]，并且 j - i 最大。

思路分析：

  1. 暴力解法：枚举所有可能的 (i, j) 对，时间复杂度 O(n²)，对于大数据会超时。

  2. 单调栈解法（推荐）：

    • 首先从左到右遍历，构建一个单调递减栈，栈中存储可能成为坡起点的索引
    • 然后从右到左遍历，对于每个位置，在栈中找到能与其形成坡的最左边的位置
    • 关键观察：如果 nums[i] >= nums[j] 且 i < j，那么索引 i 比索引 j 更有潜力成为坡的起点

  3. 排序+双指针解法：

    • 将索引按照对应的值进行排序
    • 维护遍历过的最小索引，计算最大宽度

单调栈解法最为直观且高效，时间复杂度 O(n)，空间复杂度 O(n)。

代码实现

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int n = nums.size();
        stack<int> st;
        
        // 构建单调递减栈，存储可能的起点索引
        for (int i = 0; i < n; i++) {
            if (st.empty() || nums[st.top()] > nums[i]) {
                st.push(i);
            }
        }
        
        int maxWidth = 0;
        // 从右到左遍历，寻找最大宽度坡
        for (int j = n - 1; j >= 0; j--) {
            while (!st.empty() && nums[st.top()] <= nums[j]) {
                maxWidth = max(maxWidth, j - st.top());
                st.pop();
            }
        }
        
        return maxWidth;
    }
};

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        n = len(nums)
        stack = []
        
        # 构建单调递减栈，存储可能的起点索引
        for i in range(n):
            if not stack or nums[stack[-1]] > nums[i]:
                stack.append(i)
        
        max_width = 0
        # 从右到左遍历，寻找最大宽度坡
        for j in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] <= nums[j]:
                max_width = max(max_width, j - stack.pop())
        
        return max_width

public class Solution {
    public int MaxWidthRamp(int[] nums) {
        int n = nums.Length;
        Stack<int> stack = new Stack<int>();
        
        // 构建单调递减栈，存储可能的起点索引
        for (int i = 0; i < n; i++) {
            if (stack.Count == 0 || nums[stack.Peek()] > nums[i]) {
                stack.Push(i);
            }
        }
        
        int maxWidth = 0;
        // 从右到左遍历，寻找最大宽度坡
        for (int j = n - 1; j >= 0; j--) {
            while (stack.Count > 0 && nums[stack.Peek()] <= nums[j]) {
                maxWidth = Math.Max(maxWidth, j - stack.Pop());
            }
        }
        
        return maxWidth;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxWidthRamp = function(nums) {
    let stack = [];
    let n = nums.length;
    
    // Build decreasing stack of indices
    for (let i = 0; i < n; i++) {
        if (stack.length === 0 || nums[stack[stack.length - 1]] > nums[i]) {
            stack.push(i);
        }
    }
    
    let maxWidth = 0;
    
    // Traverse from right to left
    for (let j = n - 1; j >= 0; j--) {
        while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[j]) {
            let i = stack.pop();
            maxWidth = Math.max(maxWidth, j - i);
        }
    }
    
    return maxWidth;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型单调栈解法
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：需要两次遍历数组，每个元素最多入栈和出栈各一次
  • 空间复杂度：最坏情况下栈中存储所有索引（严格递减序列）