题解 | #牛牛的魔法值#

一.题目描述
NC574牛牛的魔法值
求一个数组中每个连续子段中最大值和次最大值的异或值的最大值
图片说明
二.算法(模拟)
我们可以枚举数组中每个元素，将其作为次大值，因为它所在的连续子段中只存在一个最大值，可以去寻找右边第一个比它大的元素和左边边第一个比它大的元素，分别进行将枚举的元素和左右边最大值异或运算，得到这个连续子段中最大值和次最大值的异或的最大值，维护这个最大值，最后返回这个最大值。
图片说明
下面是完整代码：

class Solution {
public:
    int solve(int n, vector<int>& a) {
        if(a.size()==1) return 0;
        int sum=0;
        for(int i=1;i<n-1;i++){
            int l=i-1,r=i+1;
            //l,r分别表示左边最大值和右边最大值的下标
            while(l>=0&&a[l]<a[i]){
                l--;
            }
            while(r<n&&a[r]<a[i]){
                r++;
            }
            if(l>=0){
                //维护异或的最大值
                sum=max(sum,a[l]^a[i]);
            }
            if(r<n){
                //维护异或的最大值
                sum=max(sum,a[r]^a[i]);
            }
        }
        return sum;
    }
};

时间复杂度： $O(n^{2})$ 双重循环，分别是枚举和寻找最大值
空间复杂度： $O(1)$ 不需要额外的空间
优缺点：思路简单，代码实现也很简单
三.算法(栈)
利用栈来找出次最大值，遍历的时候把每一个数先当作次最大值。在寻找左边第一个比它大的元素时，将所有比它小的元素出栈，直到遇到第一个比它大的元素，取栈顶元素与当前值做异或运算，更新最大值；右边需要通过枚举来找到最大值，下面是完整代码：

class Solution {
public:
    int solve(int n, vector<int>& a) {
        if(a.size()==1) return 0;
        int sum=0;
        stack<int>st;
        for(int i=0;i<n;i++){
            //把比当前数小的数出栈
            while(st.size()&&st.top()<a[i]) st.pop();
            if(st.size()){
                //维护最大值
                sum=max(sum,a[i]^st.top());
            }
            //将数压入栈
            st.push(a[i]);
            //右边遍历找到最大值
            int r=i+1;
            while(r<n&&a[r]<a[i]){
                r++;
            }
            if(r<n){
                //对最大值进行维护
                sum=max(sum,a[i]^a[r]);
            }
        }
        return sum;
    }
};

时间复杂度： $O(n^{2})$ 双重循环，分别是枚举和寻找最大值
空间复杂度： $O(n)$ 需要额外的空间来维护栈
优缺点：思路简单，但是代码实现没有上一种算法简单，而且空间复杂度高