单调栈

一、概述：

单调栈是一种特殊的栈结构，他要维持栈内元素保持一种单调性，从而能很快速的在线判断当前元素与后进来的元素大小关系。

二、单调性质

为了维持单调性，在进栈时需要做元素的检查工作。以单调递增栈来说，如果发现要进栈的元素比目前栈顶元素小，如果此时将该元素进栈，必然会破坏单调性，所以需要对栈内元素进行调整工作：即如果该元素比栈顶元素小，则一定要将栈顶元素弹出，直到该元素不再比栈顶元素大或者栈为空时，可将该元素进栈。

三、功能用途

在进行调整工作时，由于栈内元素时刻保持单调性，所以在遇见要进栈的元素比栈顶元素小时，对于当前栈顶元素，这个要进栈的元素是它第一次见到的比它小的元素。利用这一性质，我们就发现了单调栈的一个主要用途：求一个元素左/右边第一个比它大/小的元素。

四、具体做法

对于具体怎么求比它大的元素还是比它小的元素，可以通过分析发现，求值的时机是在要进栈的元素破坏了当前栈所保持的单调性，即与当前栈保持的单调性相反。所以我们可以说：

  • 如果求比当前元素大的元素的位置，可以建立单调递减栈。

  • 如果求比当前元素小的元素的位置，可以建立单调递增栈。

那如何求左边的或者右边的目标元素位置呢？

我们稍加分析就会知道：无论求哪个方向的元素，目标元素都一定要在当前元素之后进栈。所以可以得到：

  • 求当前元素左边的比该元素大/小的元素，要从右向左依次添加。

  • 求当前元素右边的比该元素大/小的元素，要从左向右依次添加。

由于我们需要求得每个元素的目标元素位置，但在一轮循环完毕后，栈中还存在符合单调性但没出栈的元素。也就是说当前栈内的每个元素都是没有与之相匹配的目标元素位置的。这时就要根据情况单独进行处理。

通常的处理方式是在循环操作结束时，再往栈内添加一个违反单调性的并且比所有的元素都要大的最值，迫使栈中的所有元素弹出。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
//例：单调递减栈。 找当前数的左边的第一个比当前数大的值的位置。
arr[0] = 2000000100;//最后位置添加一个最值。
for(int i = N; i >= 0; i--){
    //找到了比当前栈顶大的数，更新值
    while(stk.size() && arr[i] > arr[stk.top()]){
        对该stk.top()进行需求操作。
        stk.pop();
    }
    stk.push(i);
}
//将最后一个元素弹出。
stk.pop();