单调栈简单点说就是维护一个元素满足单调性的栈，即栈内元素总是单调的

 

找出序列中某一个元素 左边/右边  第一个 比它 大/小 的元素的位置

用单调栈做的话，复杂度是 O（n） 的

 

如果要求比某一元素小的 第一个 元素的位置的话，维护递减

while(!stk.empty()) stk.pop();for(int i=0; i
     
      = arr[i]) stk.pop();    L[i] = stk.empty() ? 0 : stk.top();///如果栈为空，说明从左边开始到这个数为止，它是最小的了    stk.push(i);}while(!stk.empty()) stk.pop();for(int i=N-1; i>=0; i--){
   ///找右边第一个比它小的、维护递增    while(!stk.empty() && arr[stk.top()] >= arr[i]) stk.pop();    R[i] = stk.empty() ? N+1 : stk.top();    stk.push(i);}
     

 

如果要求比某一元素大的 第一个 元素的位置的话，维护递增

while(!stk.empty()) stk.pop();for(int i=0; i
     
      =0; i--){
   ///找右边第一个比它大的、维护递减    while(!stk.empty() && arr[stk.top()] <= arr[i]) stk.pop();    R[i] = stk.empty() ? N+1 : stk.top();    stk.push(i);}
     

 

 

裸题在此 POJ 2559

题意 : 找出柱状图中最大的长方形的面积

分析 : 枚举每一个柱子，长方形面积的高肯定就是这个柱子的高度，宽度就是到左右延伸至小于这个柱子高度的两个柱子的位置，这就是宽了，也就是找到某一元素左右第一个比其小的元素的位置在哪里，使用单调栈就轻松解决了。

#include
      
       #define LL long longusing namespace std;const int maxn = 1e5 + 10;int N, L[maxn], R[maxn];stack
       
         stk;LL H[maxn];int main(void){    while(~scanf("%d", &N) && N){        for(int i=1; i<=N; i++) scanf("%lld", &H[i]);        while(!stk.empty()) stk.pop();        for(int i=1; i<=N; i++){
    ///找左边第一个比它小的、维护递减            while(!stk.empty() && H[stk.top()] >= H[i]) stk.pop();            L[i] = stk.empty() ? 0 : stk.top();            L[i]++;            stk.push(i);        }        while(!stk.empty()) stk.pop();        for(int i=N; i>=1; i--){            while(!stk.empty() && H[stk.top()] >= H[i]) stk.pop();            R[i] = stk.empty() ? N+1 : stk.top();            R[i]--;            stk.push(i);        }        LL ans = 0;        for(int i=1; i<=N; i++)            ans = max(ans, H[i] * (LL)(R[i] - L[i] + 1));        printf("%lld\n", ans);    }    return 0;}