题解 | #牛牛的魔法值#

题目：求一个序列中每个连续子段中最大值异或次大值的最大值
方法一：双指针暴力查找
如果枚举每个元素作为最大值，则找次大值的时间复杂度比较高，因此，枚举序列中每个元素作为次大值，则在它所在的连续子段中，只有一个元素比它大，寻找左边第一个比它大的元素和右边第一个比它大的元素，分别进行异或运算得到这个连续子段中的魔法值,这里我们采用双指针查找左边和右边的最大值，注意维护最大值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示是几维空间
     * @param a int整型一维数组 表示n维空间的坐标
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        if(a.length==1)return 0;
        int res=0;
        //枚举每个元素作为次大值
        for(int i=1;i<n;i++){
            int l=i-1;
            while(l>=0&&a[l]<a[i])l--;//找a[i]左边第一个比它大的值
            if(l>=0&&a[l]>a[i])res=Math.max(res,a[l]^a[i]);
            int r=i+1;
            while(r<n&&a[r]<a[i])r++;//找a[i]右边第一个比它大的值
            if(r<n&&a[r]>a[i])res=Math.max(res,a[i]^a[r]);
        }return res;
    }
}

复杂度：
时间复杂度： ,双重循环
空间复杂度：
方法二：辅助栈
也可以用辅助栈来寻找最大值
具体做法：
用栈存储每个元素作为次大值，在寻找左边第一个比它大的元素时，将所有比它小的元素出栈，直到遇到第一个比它大的元素，取栈顶元素与当前值做异或运算，更新最大值，再从右边第一个元素枚举找到右边第一个比它大的元素，进行异或运算，更新最大值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示是几维空间
     * @param a int整型一维数组 表示n维空间的坐标
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        if(a.length==1)return 0;
        int res=0;
        Stack<Integer>s=new Stack<Integer>();
        //枚举每个元素作为次大值
        for(int i=0;i<n;i++){
            while(!s.isEmpty()&&s.peek()<a[i])s.pop();//比a[i]小的出栈
            if(!s.isEmpty())res=Math.max(res,a[i]^s.peek());//找a[i]左边第一个比它大的值
            s.push(a[i]);
            int j=i+1;
            while(j<n&&a[j]<a[i])j++;//找a[i]右边第一个比它大的值
            if(j<n)res=Math.max(res,a[i]^a[j]);
        }return res;
    }
}

复杂度：
时间复杂度： ,双重循环
空间复杂度：,辅助栈的大小不超过n