dsa

单调栈

单调栈的思想和单调队列差不多，但是维护的是一个栈。

同样的，如果要求在区间内某元素左侧或者右侧满足某个最值条件的元素，用单调栈很高效。只需要考虑「遮蔽」问题，比如说如果a和b同在左边，且a<b，那么此时如果b遮蔽了a，就维护一个递减的栈。

元素压入栈时，就可以得知关于这个元素要求的目标。元素出栈的时候，也可以得到它和当前元素的大小关系。这些信息可以被利用。

用单调栈解RMQ问题

以区间最大值问题为例，用单调栈求解，基本思路是：

1. 将所有查询[l,r)按照其右边界r排序
2. 依次处理这些排序后的查询。假设当前处理查询[l,r)，则
   1. 从上一步结束的地方开始（初始0），将数组中的元素放入单调栈中，直到位置r，并维护单调栈递减
   2. 找到单调栈中的第一个满足对应位置大于等于l的元素，这就是当前查询对应的输出
3. 将查询的结果按照排序前的次序输出。

参考

• 739. 每日温度 - 力扣（LeetCode）
• 84. 柱状图中最大的矩形 - 力扣（LeetCode）
• Bad Hair Day : 典型的单调栈应用
• P2251 质量检测 : RMQ问题，可以用单调队列/单调栈解