如名，就是在栈中的元素是有序的，故可以分为 单调递增栈 和 单调递减栈 （注意是按照出栈之后的顺序来说的）
- 单调递增栈：栈中数据出栈的序列为单调递增序列
- 单调递减栈：栈中数据出栈的序列为单调递减序列
牢记栈中数据永远是有序的
只处理一种典型的问题，叫做 Next Greater Element， 即寻找一侧第一个大于（或者小于）的边界
单调栈专门处理类似「找右边第 1 个大于自己的元素」的问题的
原因：
- 我们只关心那个最近的问题，后进先出，符合栈的使用场景；
- 又有大小关系，因此栈中每时每刻的形态就是「单调」的。
模拟实现一个递增单调栈：
现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。
-
10入栈时，栈为空，直接入栈，栈内元素为10。
-
3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。
-
7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。
-
4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。
-
12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。
即： 判断是递增还是递减栈 递增 则出栈是递增 栈内应该是递减 小于则入栈
- 栈为空或当前元素值小于栈顶元素值，则入栈
- 当前元素值大于栈顶元素，则将栈顶元素出栈，直到栈顶元素大于当前元素值 此时再入栈
具体查看代码注释
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
if not heights:
return 0
# 使用单调栈 什么是单调栈？ 需要的是两边的边界》= 当前的值 即栈内单调递增 即 单调递减栈
# 增加两个哨兵节点 减少非空判断
size = len(heights)
res = 0
heights = [0] + heights + [0]
stack = [0]
size += 2
# 第一个的判断呢？
for i in range(1, size):
while heights[i] < heights[stack[-1]]:
# 找到一个小于的元素了 那么开始可以更新答案
# 这是本轮次可以计算的 底的下标 即以 heights[top] 为底 同时i为右边界 此时的左边界呢？ 注意栈顶是 stack【-1】
# 此时的左边界 因为是单调递减栈 栈内是单调递增的 top出栈之后的下一个就是小于top元素的下标 即左边界确定
# 在这次的while 循环中
cur_height = heights[stack[-1]]
stack.pop()
# cur_height = heights[stack.pop()]
cur_width = i - stack[-1] -1
print(cur_height, cur_width)
res = max(res, cur_height*cur_width)
# 栈内没有比当前索引处高度小的了，将当前索引进栈 上面是while循环 把大于当前值的全部排出
stack.append(i)
return res
和单调栈有关的4道题目以及解析