题目描述

根据题意可知：

• 有长度为n的一维数组，数组值不重复，即对于任意一对(i,j)，a[i] != a[j]
• 对于数组的某个连续子数组a[i,j]来说，a[i,j]区间内的最大值与次大值的异或结果为该子数组的魔法值
• 数组的魔法值为其所有子数组魔法值中的最大值
• 求数组的魔法值

  示例：
  输入：10,[3,7,0,9,6,5,8,4,1,2]
  输出：15
  说明：以9和6为最大值和次大值的子数组魔法值最大，9 ^ 6 = 15

题目解析

按题目描述，使用暴力求解得到所有子数组的魔法值可求出最大值，但这样时间复杂度过大，所以不考虑。
要解决的问题

1. 题目需要对连续子数组进行操作，每个子数组需要找到最大值和次大值
2. 最终要求出异或结果中的最大值，异或运算结果大小与操作符本身的大小无直接关系，所以所有情况都要考虑到
3. 求出所有异或结果的最大值

解决思路

1. 求一段数组的最大值和次大值。
   若已知最大值难以得到次大值，若已知次大值则大于其的即为最大值。以次大值为中心，或者说数组的一段，寻找其左右两端较大的值，即为最大值，便可计算异或值。

   示例：假设a[i]为次大值
   找其左侧最大值：可以用栈栈中存放的为数组中a[i]左侧的值，依次比较栈顶元素与a[i]的大小，若栈顶元素小则直接出栈，若栈顶元素a[k]大于a[i],则为左侧最大值，则子数组a[k,i]的魔法值为a[k] ^ a[i].然后将a[i]入栈。
   找其右侧最大值：从a[i + 1]开始查找，若小于a[i]则下标加1，若大于a[i]则为最大值a[j]，子数组a[i,j]的魔法值为a[i] ^ a[j]
   通过左右两侧的查找可以得到以a[i]为次大值的子数组的魔法值

2. 计算所有异或值
   遍历数组，求出以每个数组值为次大值的子数组的魔法值，最终取最大值

3. 获得数组的魔法值
   每次求出魔法值时都取最大值，最终结果即为函数返回值

代码

public int solve (int n, int[] a) {
        // write code here
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(a[0]);
        // 子数组长度至少为2
        for(int i = 1;i < n;i++){
            // 找a[i]左侧最大值
            while(!stack.isEmpty() && stack.peek() < a[i]){
                stack.pop();
            }
            if(!stack.isEmpty()){
                ans = Math.max(ans,a[i] ^ stack.pop());
            }
            stack.push(a[i]);
            // 找a[i]右侧最大值
            int j = i + 1;
            while(j < n && a[j] < a[i]){
                j++;
            }
            if(j < n){
                ans = Math.max(ans,a[i] ^ a[j]);
            }            
        }
        return ans;
    }