单调栈

定义

  • 单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈
    • 单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大
    • 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小

规则

  • （单调递减栈）现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。
    • 0入栈时，栈为空，直接入栈，栈内元素为10。
    • 入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。
    • 入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。
    • 入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。
    • 2入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。

应用

  • 局部顺序问题，可以使用单调栈解决。例如存在一个局部增序的序列。需要找到所有的局部增序的序列。则单调增栈的每次连续入栈，都是增序。每次连续出栈都是违反增序规则的。

  • 单调递减栈：

    • 在一个队列中针对每一个元素从它右边寻找第一个比它大的元素
    • 在一个队列中针对每一个元素从它左边寻找第一个比它大的元素（从后往前遍历）

  • 可以以 O(1) 的时间复杂度得知某个位置左右两侧比他大（或小）的数的位置，当你需要高效率获取某个位置左右两侧比他大（或小）的数的位置的的时候就可以用到单调栈。

    • 求解数组中元素右边第一个比它小的元素的下标，从前往后，构造单调递增栈；比它小的元素会将其pop掉。
    • 求解数组中元素右边第一个比它大的元素的下标，从前往后，构造单调递减栈；比它大的元素会将其pop掉。
    • 求解数组中元素左边第一个比它大的元素的下标，从后往前，构造单调递减栈；比他大的元素会将其pop掉
    • 求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递增栈。比他小的元素会将其pop掉。

代码

  • 单调递增栈
1
2
3
4
5
6
for(int i = 0; i < T.size(); i++){
  while(! stk.empty() && stk.top() > T[i]){
    ​stk.pop();
  }
  stk.push(A[i]);
}
  • 单调递减站
1
2
3
4
5
6
for(int i = T.size() - 1; i >= 0; i--){
  while(! stk.empty() && T[i] >= stk.top()){
    stk.pop();
  }         
  stk.push(i);
}

特性

单调栈的关键不在于栈的顺序，不在于是递增栈还是递减栈。

  1. 出栈入栈的时候所处的状态。
  2. 出栈入栈的时候所采取操作。

以递减栈为例。

  1. 当元素出栈的时候，说明后续有更大的元素，栈底的元素也比自己大。所以出栈元素是倒数第二大的元素。
  2. 当元素入栈的时候，之前的元素都比自己大的状态。并不知道正向是第几大的元素。

递增栈则相反

  1. 当前元素出栈的时候，说明当前元素是倒数第二小的元素。

问题总结

一般会采取怎样的操作呢？具体再总结。

其它类型的单调栈

  • 求最大区间：利用的出栈的序列。表示一个可能的最大值区间。
  • 132模式：利用了其有序性。

总结

综上所述主要有以上三种利用思想。

  1. 针对栈内元素数量的利用。第一个问题，仅仅是简单的模拟。
  2. 针对有序性的利用。每次都是贪心的求得最大的3，反向求解第二大的元素。
  3. 针对出栈序列的利用。在递增栈和递减栈中，每一个出栈序列的两端，都是一个最大边界、或者最小边界，在边界中会形成问题的一个解序列。序列中的每个值，比两个边界大或者小。