题解 | #牛牛的魔法值#
牛牛的魔法值
http://www.nowcoder.com/practice/4d7d8a61ad2f4c9b9f130a35a97b49f5
题意：给定一个数组，每个元素的值不重复。
对于每一个子连续区间，它的值是该子连续区间最大值与次大值的异或值。
遍历每个子连续区间，使异或值最大。
方法一：
模拟
思路：遍历数组的每一个元素，使之作为次大值，然后分别向左、向右找到第一个大于次大值的数当做最大值。并求解区间中最大值与次大值的异或值，维护该异或值，使其最大化。
注意：为什么不用最大值取寻找次大值？因为通过最大值向左、向右找到第一个小于最大值的数当做次大值时，那么中间的值肯定是大于最大值的，所以原先设置的最大值就不是这段区间的最大值，相矛盾，故错误。
class Solution {
public:
int solve(int n, vector<int>& a) {
int res=0;
for(int i=0;i<n;i++){//遍历每个元素作为次大值
int j=i-1,k=i+1;
while(j>=0&&a[j]<a[i])//向左寻找第一个最大值
j--;
while(k<n&&a[k]<a[i])//向寻右找第一个最大值
k++;
if(j>=0)
res=max(res,a[j]^a[i]);
if(k<n)
res=max(res,a[k]^a[i]);
}
return res;
}
};
时间复杂度：%EF%BC%8C%E4%B8%A4%E5%B1%82%E5%BE%AA%E7%8E%AF%EF%BC%8Cn%E4%B8%BA%E6%95%B0%E7%BB%84%E5%A4%A7%E5%B0%8F)
空间复杂度：%2C%E6%97%A0%E9%9C%80%E9%A2%9D%E5%A4%96%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
栈优化
思路：沿用方法一的思想，而从右到左寻找第一个大于次大值(即）的值可以用栈来实现。
数组元素依次入栈，当栈非空且栈顶元素小于a[i]时，栈顶元素出栈。
class Solution {
public:
int solve(int n, vector<int>& a) {
int res=0;//异或值的最大值
stack<int> s;
for(int i=0;i<n;i++){
while(!s.empty()&&s.top()<a[i])//当栈非空且栈顶元素小于a[i]时，栈顶元素出栈
s.pop();
if(!s.empty())//如果栈没空，则找到
res=max(res,s.top()^a[i]);
s.push(a[i]);//入栈
int j=i+1;
while(j<n&&a[j]<a[i])
j++;
if(j<n)
res=max(res,a[j]^a[i]);
}
return res;
}
};
时间复杂度：%EF%BC%8Cn%E4%B8%BA%E6%95%B0%E7%BB%84%E5%A4%A7%E5%B0%8F)
空间复杂度：%2Cn%E4%B8%BA%E6%95%B0%E7%BB%84%E5%A4%A7%E5%B0%8F%E3%80%82)
查看7道真题和解析
