思路：
题目的主要信息：
- 数组a长度为n，且数字不重复，数组长度不为0
- 对于数组的某个连续子数组
而言，
- 整个数组中所有子区间的魔法值的最大值就是数组的魔法值，求这个值
方法一：数组模拟单调队列
具体做法：
如果我们找到了一个区间的最大值想要再找到次大值需要再次遍历一遍，很麻烦，于是我们可以考虑用一个单调队列保存数组内的值，使之成递减序，而我们每次遇到一个元素就可以在单调队列中往前寻找比
更大的一个数，这其中的区间这两个数就是最大值和次大值，我们取异或然后更新答案即可。这是往后遍历的情况，但是我们不能保证最大值一定出现次大值前面，因为单调队列中保存的都是之前那出现过的数字，因此我们还需要从后往前再来一遍，即遇到
要寻找它左侧的最大值，也要寻找它右侧的最大值。
class Solution {
public:
int solve(int n, vector<int>& a) {
int res = 0;
vector<int> q(n + 1); //单调队列
int left = 1, right = 1;
q[right] = a[1];
//分别计算左右寻找最大值
for(int i = 2; i < n; i++){
while(left <= right && q[right] < a[i]) //找到左边第一个比a[i]大的
right--;
if(left <= right)
res = max(res, a[i] ^ q[right]); //维护最大
right++;
q[right] = a[i];
}
left = 1, right = 1;
q[right] = a[n - 1];
for(int i = n -2; i > 0; i--){
while(left <= right && q[right] < a[i]) //找到右边第一个比a[i]大的
right--;
if(left <= right)
res = max(res, a[i] ^ q[right]);
right++;
q[right] = a[i];
}
return res;
}
};复杂度分析：
- 时间复杂度：
，最多循环
次，因为内循环总共只有
次
- 空间复杂度：
方法二：栈模拟单调队列
具体做法：
我们也可以用栈来模拟之前的单调队列，只要栈顶元素较小，越往栈底越大即可。具体操作同方法一，也是遇到一个可以将其视作次大值，然后不断弹出栈顶比其小的元素的，直到找到该区间的最大值，这是找左边的，而右边遍历找到第一个比
大的元素即可，然后将
加入栈中，使之成为顶部较小元素，即可寻找下一个。
class Solution {
public:
int solve(int n, vector<int>& a) {
int res = 0;
stack<int> s; //栈中存递增
s.push(a[0]); //数组长度不为0
for(int i = 1; i < n; i++){
//以a[i]为次大值
while(!s.empty() && s.top() < a[i]) //找到左边的最大值
s.pop();
if(!s.empty())
res = max(res, a[i] ^ s.top());
s.push(a[i]);
int k = i + 1; //找到右边的最大值
while(k < n && a[k] < a[i])
k++;
if(k != n)
res = max(res, a[k] ^ a[i]);
}
return res;
}
};复杂度分析：
- 时间复杂度：
- 空间复杂度：
京公网安备 11010502036488号