题解

• 解法一: 的算法，我们直接暴力把所有子维度区间的魔法值算出来。
• 解法二： 的时间复杂度，我们考虑使用单调栈。因为计算一个子维度区间的魔法值，只需要考虑最大维度和次大维度，因此我们假设现在要选取i号点，无非就是在它左边和右边找到第一个比他大的维度值去计算答案，为什么是第一个比他大的而不是第二个或者第N个呢，因为如果选取第二大的，那么计算贡献的时候就是计算第一个比你大的和第二个比你大的。然后我们可以通过一个单调递增的栈来进行维护，从左往右扫一遍，再从右往左扫一遍即可。

class Solution {
public:
    /**
     * 返回一个数字表示魔法值。
     * @param n int整型 表示是几维空间
     * @param a int整型vector 表示n维空间的坐标
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        // write code here
        int maxn=0;
        stack<int>S;
        for (int i=n-1; i>=0; i--)
        {
            while (S.size()!=0 && S.top()<a[i])
            {
                S.pop();
            }
            if (S.size()!=0)
            {
                int tmp=S.top()^a[i];
                maxn=max(maxn,tmp);
            }
            S.push(a[i]);
        }
        while (S.size()!=0) S.pop();

        for (int i=0; i<=n-1; i++)
        {
            while (S.size()!=0 && S.top()<a[i])
            {
                S.pop();
            }
            if (S.size()!=0)
            {
                int tmp=S.top()^a[i];
                maxn=max(maxn,tmp);
            }
            S.push(a[i]);
        }
        return maxn;
       }
};