引入：一道编程题
给一个长度为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）
- 4要入栈，4大于1，则入栈：（1,4）
- 3要入栈，弹出4,3进栈（1,3）
- 6要入栈，入栈：（1,3,6）
- 0要入栈：（0）
这里可以是单调递增栈，从左向右读入数据，可以看到我们可以很容易找到这个数左边第一个比它小的数
例题
https://segmentfault.com/a/1190000004023326
