难度: Medium
给定一个整数数组 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.
提示：
2 <= A.length <= 500000 <= A[i] <= 50000运行时间: 45 ms
内存: 21.6 MB
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
"""
对于i元素, 找到右侧距离它最远的j, nums[j] >= nums[i]
1.构造单调递减栈, 栈内存放的是坡底bottom
2.从后往前遍历数组,作为坡顶top
如果bottom > top, 跳过
如果bottom <= top, 记录宽度, bottom弹出, 继续查看bottom
"""
st = []
for i, x in enumerate(nums):
if not st or nums[st[-1]] > x:
st.append(i)
ans = 0
for j in range(len(nums)-1, -1, -1):
while st and nums[j] >= nums[st[-1]]:
i = st.pop()
ans = max(ans, j-i)
return ans
该题解采用单调栈的方法来求解最大宽度坡问题。首先，构建一个单调递减栈，栈中存储数组元素的索引，确保栈中的元素对应的数组值是递减的。这样做的目的是为了后面从数组尾部开始向前遍历时，能快速找到满足条件的坡底（即数组中较小的值）。在遍历过程中，对于每个元素，试图找到一个坡底，使得坡底的值不大于当前元素的值。如果找到了这样的坡底，那么计算当前的宽度（当前索引减去坡底索引），并更新最大宽度。重复这个过程直到遍历完数组或栈为空。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
# 初始化单调递减栈
st = []
for i, x in enumerate(nums):
# 如果栈为空或当前元素小于栈顶元素对应的值，将当前索引入栈
if not st or nums[st[-1]] > x:
st.append(i)
ans = 0
# 从后向前遍历数组，尝试找到最大宽度的坡
for j in range(len(nums)-1, -1, -1):
# 当栈不为空且当前元素大于等于栈顶元素对应的值时
while st and nums[j] >= nums[st[-1]]:
i = st.pop() # 弹出栈顶元素（坡底索引）
ans = max(ans, j-i) # 更新最大宽度
return ans
在构建单调递减栈的过程中，目标是保持栈内元素对应的数组值是递减的。这样做的原因是，栈中每个元素的索引代表了一个潜在的坡底。如果遇到一个较小的元素，将其索引入栈，可以确保在后面寻找坡顶时，能找到尽可能早的坡底索引，从而最大化坡的宽度。如果当前元素大于或等于栈顶元素，则意味着它不能作为一个有效的更早的坡底，因为它在数组中的位置更靠后，且值不小于前面的元素。
从后向前遍历数组时，目标是找到一个有效的坡顶，即数组中较大的值，且能与栈中记录的坡底索引形成最大宽度的坡。检查当前元素是否大于等于栈顶元素对应的值是为了确保找到一个有效的坡顶（当前元素）和坡底（栈顶元素对应的值）。只有当当前元素大于等于栈顶元素时，当前的索引与栈顶索引之间才符合坡的定义（坡顶不小于坡底），因此可以计算宽度并尝试更新最大宽度。
弹出栈顶元素的条件是当前元素（从数组末端向前遍历时的元素）必须大于等于栈顶元素对应的值。这一条件的选择是因为，一旦当前元素大于等于栈顶元素，说明找到了一个有效的坡顶，与栈顶元素对应的坡底可以形成一个坡。此时，可以计算当前坡的宽度，并更新可能的最大宽度。此外，弹出栈顶元素后，栈中下一个元素（如果存在）将成为新的坡底候选，可以继续检查是否能形成更宽的坡。
如果数组中包含重复元素，单调栈方法仍然有效。在构建单调递减栈时，如果当前元素等于栈顶元素，通常不会将其索引入栈，因为已经有一个相同值的索引，且位置更靠前。这保证了在后续寻找坡顶时，可以保持最大的宽度。但需要注意，当从数组末端向前遍历时，遇到与栈顶元素相等的情况，同样可以形成坡，并尝试更新最大宽度，因为这样可以利用到重复值之间的宽度。