单调栈也是栈，特别之处在于栈内的元素都保持有序（单调递增或单调递减）。
它通常只处理一类典型的问题，叫做 Next Greater Element：“给你一个数组，返回一个等长的数组，对应索引存储着向右找的下一个更大元素，如果没有更大的元素，就存 -1。”当然，“向右找的下一个更小元素”、
“向左找的下一个更大元素”等也是这一类的。
1: 当前项向右找第一个比自己大的位置 —— 从右向左维护一个单调递减栈
def nextGreaterElement_01(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length - 1, -1, -1):
# 想一想比较时用 “<=” 与 “<” 有什么区别吗？
while stack and stack[-1] <= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
# 如果栈为空，则为默认值 -1，代表不存在这样的数
stack.append(nums[i])
return res
或者 —— 从左向右维护一个单调递减栈
def nextGreaterElement_011(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
res[idx] = nums[i]
stack.append(i)
return res
不难发现，这样操作更难想到，因此知道就好，一般用方法一即可。
2：当前项向右找第一个比自己小的位置 —— 从右向左维护一个单调递增栈
def nextGreaterElement_02(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length - 1, -1, -1):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
3: 当前项向左找第一个比自己大的位置 —— 从左向右维护一个单调递减栈
def nextGreaterElement_03(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and nums[stack[-1]] <= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
4: 当前项向左找第一个比自己小的位置 —— 从左向右维护一个单调递增栈
def nextGreaterElement_04(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and stack[-1] >= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
总结一下：
- 当前项向右找第一个比自己大的位置 —— 从右向左维护一个单调递减栈
- 当前项向右找第一个比自己小的位置 —— 从右向左维护一个单调递增栈
- 当前项向左找第一个比自己大的位置 —— 从左向右维护一个单调递减栈
- 当前项向左找第一个比自己小的位置 —— 从左向右维护一个单调递增栈
即：“当前项向右（左）找”就“从右向左（从左向右）维护栈”，“找第一个比自己小（大）的” 就用“单调递增（减）栈”。
有很多问题还可以转化为 Next Greater Element 来处理。比如 42. 接雨水：
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
不难发现，积水的凹处都是两边高中间低的地方；那么对于一个元素，只要向右找到第一个 比它高的元素即可开始结算积水面积。然而这样会出现重复结算的问题，可以用哈希表避免， 但是更优的方法是把结算逻辑放在单调栈弹出元素时：
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
stack = []
for i in range(len(height) - 1, -1, -1):
# 从右向左维护一个单调递减栈
while stack and height[stack[-1]] < height[i]:
h0 = height[stack.pop()]
if stack:
h1 = min(height[i], height[stack[-1]])
ans += (h1 - h0) * (stack[-1] - i - 1)
stack.append(i)
return ans
这里其实都是找离当前项最近的元素，还有一类问题我将其称为 Furthest Greater Number，
它是找离当前项最远的更大的元素。例如：
962. 最大宽度坡
给定一个整数数组 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 <= 50000
0 <= A[i] <= 50000
这同样是利用单调栈来解决的，不过用法有所不同：
class Solution:
def maxWidthRamp(self, A: List[int]) -> int:
stack = []
for j, num in reversed(list(enumerate(A))):
if not stack or num >= A[stack[-1]]:
stack.append(j)
ans = 0
for i, num in enumerate(A):
while stack and A[stack[-1]] >= num:
ans = max(ans, stack.pop() - i)
return ans
