单调栈

引入：一道编程题

给一个长度为N的个不相同的序列，找出所有区间中最大值和第二大数的异或值最大的值;

分析：对于所有区间只需要找其最大值和第二大数，所以对于很多区间的结果是重复的，对于每一个数，它起作用的区间只有在其前面最多只有一个数是大于它的，可以用一个单调递减栈来做，对于每一个新的数a[i]，在它前面第一个大于它的数 a[j]和第二个大于它的数之间的数到 a[i] 的区间的数的最大值和第二大数为a[j] , a[i]，只需要找a[i],a[j]的所有区间所有情况.

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn = 100010;
int s[maxn];
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        int top = -1;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int t;
            scanf("%d", &t);
            // top 栈顶 单调递减栈
            while (top != -1 && s[top] < t){ 
                ans = max(ans, t^s[top--]); 
            }
            if (top != -1)
                ans = max(ans, t^s[top]);
            s[++top] = t;
        }
        printf("%d\n", ans);
    }
    return 0;
}

单调栈的性质

• 栈内的元素，按照某种方式排序下（单调递增或者单调递减），如果新入栈的元素破坏了单调性，就弹出栈内元素，直到满足单调性。

• 作用：可以很方便求出某个数的左边或者右边第一个比它大或者小的元素，时间复杂度为O（N）

• 进展操作（单调递增栈）：每次进栈检验栈顶元素和进栈元素e的大小，如果栈顶元素小于e，则直接入栈，如果大于等于e，则出栈，直到栈空或者栈顶元素小于x

• 例子：1 4 3 6 0

  1. 1入栈：（1）
  2. 4要入栈，4大于1，则入栈：（1,4）
  3. 3要入栈，弹出4,3进栈（1,3）
  4. 6要入栈，入栈：（1,3,6）
  5. 0要入栈：（0）

  这里可以是单调递增栈，从左向右读入数据，可以看到我们可以很容易找到这个数左边第一个比它小的数

例题

• 待补充
  http://blog.163.com/scuqifuguang@126/blog/static/171370086201122412630525/

https://segmentfault.com/a/1190000004023326

参考：

• 单调栈和单调队列