JZX轻语：简
LeetCode 962 - 最大宽度坡
发表于2024年05月29日
朴素的做法是对于每一个元素，在其左侧的子数组中从左往右检查第一个小于等于它的元素，并更新上述最长的距离。这种双重循环会超时，需要想办法复用前面已遍历元素的大小数据。这种综合大小+索引情况可以考虑单调栈。对于此问题，可以利用单调栈维护已遍历数组以arr[0]开头的最长递减序列，在此单调栈中，每个元素在索引上递增，而在大小关系递减，最长递减序列意味着栈中每个元素的右侧元素是原数组中其右侧第一个比它小的。由此，朴素做法可以优化为：对于每个元素，如果其比栈顶元素小，则不存在这样的数对，追加到栈顶；否则，通过二分法在栈中找到比它小的最大元素，更新距离即可。
更进一步地解释：比如当前的栈为[(10, 0), (8, 7)]，说明第一个元素10右边中，第一个比它小的元素为8，下标为7；而arr[1..6]区间的元素都比10大。这样的意义为，对于右边的元素，如果它比arr[1..6]任一元素大，那么它必定比10大。而栈中比它小的最大元素，左侧不会有比它小的了！
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
ans = 0
stack = []
for i, num in enumerate(nums):
if not stack or stack[-1][0] > num:
stack.append((num, i))
else:
lo, hi = 0, len(stack) - 1
while lo <= hi:
mid = (lo + hi) >> 1
if stack[mid][0] > num:
lo = mid + 1
else:
hi = mid - 1
if lo < len(stack):
ans = max(ans, i - stack[lo][1])
return ans超时的朴素版本：
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
ans = 0
for i, num in enumerate(nums):
for j in range(0, i):
if i - j <= ans:
break
if nums[i] >= nums[j]:
ans = i - j
break
return ans