本人总结的单调栈大概有三类:
- 求右边第一个比该元素大(小)的元素
- 求左边第一个比该元素大(小)的元素
- 求两边比该元素大(小)的元素
前两类一般是中等难度的题,完成一次单调栈即可,最后一类是困难难度,需要完成两次单调栈。
进一步地:
(1)求右边第一个比该元素大(小)的元素,采用倒序遍历:for i in range(n-1,-1,-1):
- 求比该元素大的元素:单调栈stack总是保存当前最大的,小于等于当前的都pop出去while stack and stack[-1] <= current: pop
- 求比该元素小的元素:单调栈stack总是保存当前最小的,大于等于当前的都pop出去while stack and stack[-1] >= current: pop
(2)求左边第一个比该元素大(小)的元素,采用正序遍历:for i in range(n):
- 求比该元素大的元素:单调栈stack总是保存当前最大的,小于等于当前的都pop出去while stack and stack[-1] <= current: pop
- 求比该元素小的元素:单调栈stack总是保存当前最小的,大于等于当前的都pop出去while stack and stack[-1] >= current: pop
推荐的刷题顺序:
(1)中等
670. 最大交换
(2)困难
84. 柱状图中最大的矩形
85. 最大矩形
42. 接雨水