《栈》专题

关于栈的算法。

1. 单调栈

应用：对于数列中的每一个数，用单调栈可以求出它的左边离它最近的且比它小或大的数的位置。
我们以左侧最近最小元素为例

/*对给定的arr无序数组操作*/
for(int i = 0; i<n; i++）
{
    //某元素arr[i]左边且比它大的值，在后续的判断中一定不是答案（arr[i]比他们都离后续待判断的元素更近一点），把他们剔除，以此使得我们的栈中元素保持单调递增。
    while(!stack.empty()&&stack.top()>=arr[i]) stack.pop(); //这里一定要>=，否则会有重复元素，改成<=就变成求左侧最大元素了
    //经过上面的消除，如果栈不为空的话，栈顶元素就是答案
    if(!stack.empty()) getAnswer; 
    //否则，这个元素左边压根就没有比它小的元素
    else noOneLessThanMe;
    
    stack.push(a[i]);
}