题解

难度：中等难度

知识点：单调栈

单调栈：

那么单调栈有这样的性质：对于单调递增的栈，如果此时栈顶元素为 b，加入新元素 a 后进行更新时：

如果 a 大于 b，说明 a 在数组里不能再往左扩展了（由于单调栈的单调递增性质，b前面的元素均小于a），也就是说，如果从 a 在数组中的位置开始往左边遍历，则 a 一定是第一个比 b 大的元素；

如果 a 小于 b，说明在数组里，a 前面至少有一个元素不能扩展到 a 的位置(至少有b元素，因为b的值要大于a，如果此时再加入新的a，那么单调栈便不再单调，所以元素a此时不能压入栈顶，因为这并不是元素a"应该"在的位置，只有当元素a找到自己的位置时元素a方能压入栈中，而这样做的前提是不改变单调栈的单调性)，也就是对于这些元素来说，a 是其在数组右侧第一个比它小的元素。

单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。

单调栈的性质：

1.单调栈里的元素具有单调性

2.元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除

3.使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。

【注】对于第三条性质的解释（最常用的性质）：为什么使用单调栈可以找到元素向左遍历第一个比他大的元素，而不是最后一个比他大的元素呢？我们可以从单调栈中元素的单调性来解释这个问题，由于单调栈中的元素只能是单调递增或者是单调递减的，所以我们可以分别讨论这两种情况（假设不存在两个相同的元素）：

2.当单调栈中的元素是单调递减的时候，则有：

（1）.当a < b 时，则将元素a插入栈顶，新的栈顶则为a

（2）.当a > b 时，则将从当前栈顶位置向前查找（边查找，栈顶元素边出栈），直到找到第一个比a大的数，停止查找，将元素
插入栈顶（在当前找到的数之后，即此时元素a找到了自己的“位置”）

本题思路：

例：5 2 1 4 3
构造单调栈：
1.首先将5压入栈中。此时栈中元素：5

2.判断2与5的大小，应为2<5,那么若2为次大的数，因此子序列为5 2 此时栈中元素：5 2

3.判断1与2的大小，应为1<2,那么若1是次大的数，因此子序列为2 1 此时栈中元素：5 2 1

4.判断4与1的大小，应为4>1 ,可以得到子序列 1 4 ；弹出栈顶元素1，继续判断 4>2, 此可以得到子序列 2 1 4，弹出栈顶元素2 ，继续判断4<5,可以得到子序列 5 2 1 4。不在继续，因为按照单调递增栈，若还存在元素一定大于5，此时4不可能为次大的数。此时栈中元素：4

5.判断3<4,此时子序列 4 3。栈中元素4 3。

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int main(){
    int n,i,res=0,x;
    stack<int> s;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>x;
        while(s.size()&&s.top()<=x){
            res=max(res,x^s.top());
            s.pop();
        }
        if(s.size()) res=max(res,x^s.top());
        s.push(x);
    }
    cout<<res;
    return 0;
}