江湖流传着一种所谓的“单调栈”的应用
其实这是栈的一个特殊用法，通常实践中不需要真的构建一个单调栈数据结构。我们只需要对一个顺序容器稍微控制一下它的进出次序，就能达到想要的效果。
单调栈的意图是在栈顶的元素始终保持着最大或者最小。
以递增栈为例。我们把一组无序的序列一次加入单调栈
8, 6, 5, 10, 2, 7, 11, 4
构建一个空栈
- 第一步，将8 加入栈中；——这一步没有什么特别的
- 第二步，将6 加入栈中; —— 6 < 8 (栈顶)元素，这样从顶到底依次递增，，没毛病。这一步还是没什么特别
- 第三步，将5 加入栈中
- 第四步， 将10入栈，由于10 > 5 因此，第三步入栈的 5 需要弹出，直到弹完，最后加入 10；这时候栈内只有一个元素10
- 第五步，接着入2，由于 2 < 10 , 没毛病。 栈内元素有2个： 2 ，10
- 第六步，加入7. 因为 7 > 2 , 弹出 2 ，栈内元素继续保持2个：7, 10
- 第七步，加入11 ，因为11 > 7, 依次弹出7， 10 ，加入11
- 第八步，加入 4，因为4 < 11 ； 4加入栈，栈内元素 11，4
整个过程保持栈内总顶部到底部一次递增的关系，并且每个元素必须要入栈。
这种奇怪的次序有什么作用？
可以看出每次需要弹出元素的时候，遇到一次数是数组中每个元素右侧第一个比它大的元素。
有点拗口
比方说第一余姚需要弹出的时候，是数字10，这表明前面的 8， 6， 5 的右侧第一个较大元都是10，我们用一个新的映射数组 N 表示
N[8] = 10
N[6] = 10
N[5] = 10
第二次弹出2 的时候，遇到的元素是 7，所以这里
N[2] = 7
第三次遇到11 的时候，接连弹出 7， 10
因此
N[10] = 11
N[7] = 11
11, 4 没有出现弹出，所以记作
N[11] = -1
N[4] = -1
我们来编写一下这个程序——计算数组下一个更大元是什么，没有就是 -1
def next_greater(array: list) -> dict:
d = defaultdict(default=-1)
st = [] # a list but can be used as a stack
for item in array:
d[item] = -1
while len(st) > 0 and st[-1] < item:
i = st.pop()
d[i] = item
st.append(item)
return d
这里的栈实际上维护的就是一个单调递增栈——每个新的元素进来之后保证栈顶到栈底单调递增。
我们来它的另一个应用——接雨水
接雨水是一个最优问题——使用动态规划可以用记忆搜索的方法算出每根柱子左边最大，右边最大，然后计算出最多的接水量。
实际上还可以用单调栈的方式计算每根柱子左侧最近一根最高，右侧最近的一根最高柱，此时意味着当前的柱子可以蓄水。
def trap(self, height: List[int]) -> int:
st = []
water = 0
for i, h in enumerate(height):
while len(st) > 0 and height[st[-1]] < h:
h_top_index = st.pop()
if len(st) == 0:
break
h_left_index = st[-1]
width = i - h_left_index - 1
water += (min(height[h_left_index], h) - height[h_top_index]) * width
# 每次遇到一个高于栈顶元素的新元素，就可以结算一次
st.append(i)
return water
单调栈为什么这么好用？
首先它的令人迷惑的进出顺序控制一点都不令人舒服，之所以在诸多应用中被采用——是因为它有很好的性能。
一个序列用单调栈存储，一般可以取得O(n) 的时间性能尺度。
直观的看，并不容易看出来这点，但是如果我们从另一个角度分析，每个元素永远都是只进一次，只出一次，总操作数就是2你次，而栈的入栈出栈操作室 O(1) 的，所以摊还下来，单调栈的平均操作时间都是 O(1)
处理一个序列只跟这个序列的长度 你有关。
