962.最大宽度坡

最大宽度坡

给定数组 nums，坡 (i, j) 满足 i < j 且 nums[i] <= nums[j]。返回最大宽度。

示例 1:

输入：nums = [6,0,8,2,1,5]
输出：4

示例 2:

输入：nums = [9,8,1,0,1,9,4,0,4,5]
输出：3

提示:

• 1 <= nums.length <= 40000
• 0 <= nums[i] <= 10^9

解析

使用单调递减栈记录可能作为左端点的索引，然后从右向左遍历寻找最大宽度。

var maxWidthRamp = function (nums) {
  const stack = [];
  for (let i = 0; i < nums.length; i++) {
    if (stack.length === 0 || nums[i] < nums[stack[stack.length - 1]]) {
      stack.push(i);
    }
  }

  let result = 0;
  for (let j = nums.length - 1; j >= 0; j--) {
    while (stack.length > 0 && nums[j] >= nums[stack[stack.length - 1]]) {
      result = Math.max(result, j - stack.pop());
    }
    if (stack.length === 0) break;
  }

  return result;
};

时间复杂度 O(N)，空间复杂度 O(N)。