962. 最大宽度坡

🟠   🔖  栈 数组 单调栈  🔗 力扣 LeetCode

题目

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.

Given an integer array nums, return _the maximum width of aramp in _nums. If there is no ramp in nums, return 0.

Example 1:

Input: nums = [6,0,8,2,1,5]

Output: 4

Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.

Example 2:

Input: nums = [9,8,1,0,1,9,4,0,4,1]

Output: 7

Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

Constraints:

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

题目大意

给定一个整数数组 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

解题思路

1. 单调递减栈法：

   • 通过维护一个 单调递减栈 存储可能成为坡起点的索引 i，确保栈顶元素对应的值 nums[i] 是比其后的任何值都要大或相等的。
   • 当从左到右遍历数组时，如果当前元素 nums[i] 比栈顶元素对应的值小，那么就将其索引 i 压入栈中，这保证了栈中存储的是可能成为坡的起点的索引。

2. 从右向左遍历寻找最大坡：

   • 构建好单调递减栈之后，从右向左遍历数组，尝试找到满足条件 nums[i] <= nums[j] 的最大坡宽度。
   • 如果发现当前元素 nums[j] 大于或等于栈顶索引对应的元素 nums[stack顶]，那么计算 j - i 的差值，并更新最大坡宽度。此时，弹出栈顶元素，因为它已经形成了最宽的坡，无法再与后续的 j 配对。

复杂度分析

• 时间复杂度：O(n)，遍历数组两次，一次是构建单调栈，一次是从右向左检查坡的宽度。
• 空间复杂度：O(n)，栈最多会存储 n 个索引。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxWidthRamp = function (nums) {
	let stack = [],
		maxWidth = 0;

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

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