引入：一道編程題
給一個長度為N的個不相同的序列，找出所有區(qū)間中最大值和第二大數(shù)的異或值最大的值;
分析：對于所有區(qū)間只需要找其最大值和第二大數(shù)剂碴，所以對于很多區(qū)間的結(jié)果是重復(fù)的，對于每一個數(shù)轻专，它起作用的區(qū)間只有在其前面最多只有一個數(shù)是大于它的忆矛，可以用一個單調(diào)遞減棧來做，對于每一個新的數(shù)a[i]请垛，在它前面第一個大于它的數(shù) a[j]和第二個大于它的數(shù)之間的數(shù)到 a[i] 的區(qū)間的數(shù)的最大值和第二大數(shù)為a[j] , a[i]催训，只需要找a[i],a[j]的所有區(qū)間所有情況.
#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 棧頂 單調(diào)遞減棧
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;
}
單調(diào)棧的性質(zhì)
棧內(nèi)的元素，按照某種方式排序下（單調(diào)遞增或者單調(diào)遞減）宗收，如果新入棧的元素破壞了單調(diào)性漫拭，就彈出棧內(nèi)元素，直到滿足單調(diào)性混稽。
作用：可以很方便求出某個數(shù)的左邊或者右邊第一個比它大或者小的元素采驻，時間復(fù)雜度為O（N）
進展操作（單調(diào)遞增棧）：每次進棧檢驗棧頂元素和進棧元素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）
這里可以是單調(diào)遞增棧昭雌，從左向右讀入數(shù)據(jù)复唤，可以看到我們可以很容易找到這個數(shù)左邊第一個比它小的數(shù)
例題
https://segmentfault.com/a/1190000004023326
