NC574 题解 | #牛牛的魔法值#

题意分析

• 给出一个序列，这个序列的数字都是不一样的，我们需要找出所有的子序列里面的最大值和次大值的异或的结果中的最大值。

思路分析

• 题目的意思已经很明显了。我们需要找到最大值和次大值。但是我们发现数据范围太大，直接暴力会被TLE。所以，我们要相办法进行优化。我们发现，在我们直接暴力枚举的时候，其实有很多的数字我们是没有必要进行重复的枚举的。比如我们枚举a[i]的数字的时候找到了左边的最大值，但是我们枚举a[i+1]的时候枚举了很多没有必要的，之前a[i]枚举过的数字。所以时间复杂度就上去了。但是，我们发现最大值和次大值其实可以用一个栈来进行维护，这里我一开始想的是枚举最大值，利用栈找出次大值。但是发现这样会有问题。当我们找次大值的时候，我们不知道当前比这个数字小的是否异或下来是最优的。所以我们可以枚举次大值，利用栈维护最大值。这样当我们找到一个最大值的时候，我们就会发现这个最大值和次大值一定是这某一个区间里面的最大值和次大值。这里可以自己好好体会。

• 这里结合样例2进行解释一下

• 但是我们枚举的之后需要做两遍操作，一种是从左往右维护最大值。另一种是从右往左维护最大值。

写法一 C++版

• 代码如下
  • 正反方向遍历一遍，时间复杂度为
  • 利用栈存储序列的数字，空间复杂度为

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示是几维空间
     * @param a int整型vector 表示n维空间的坐标
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        // write code here
        stack<int> st;
        int ans=0;
        st.push(a[0]);
        // 从左往右遍历，找每个数左边比这个数字大的数
        for(int i=1;i<n;i++){
            while(!st.empty()){
                // 如果栈顶的元素比这个数字小，那么出栈
                if(st.top()<a[i]){
                    st.pop();
                }else{
                    // 维护一个最大值
                    ans=max(ans,a[i]^st.top());
                    break;
                }
            }
            st.push(a[i]);
        }

        while(!st.empty()){
            st.pop();
        }

        // 从右往左遍历，找到每个数字右边比这个数字大的数字
        st.push(a[n-1]);
        for(int i=n-2;i>=0;i--){
            while(!st.empty()){
                // 如果栈顶的元素比这个数字小，那么出栈
                if(st.top()<a[i]){
                    st.pop();
                }else{
                    // 维护一个最大值
                    ans=max(ans,st.top()^a[i]);
                    break;
                }
            }
            st.push(a[i]);
        }

        return ans;
    }
};

写法二 Go语言版

• 由于Go里面没有栈这个封装好的。所以我们可以使用一个切片来模拟栈的操作。
• 代码如下
  • 正反方向遍历一遍，时间复杂度为
  • 利用栈存储序列的数字，空间复杂度为

package main
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 表示是几维空间
 * @param a int整型一维数组 表示n维空间的坐标
 * @return int整型
*/
func solve( n int ,  a []int ) int {
    // write code here
    // 利用一个切片模拟栈的操作
    var stack = make([]int,n)
    stack[1]=a[0]
    ans := 0
    top := 1
    for i:=1; i<n; i++ {
        for top>0 {
            // 如果栈顶元素小于当前元素
            if stack[top] < a[i] {
                top--
            }else{
                // 维护最大值
                tmp := a[i]^stack[top]
                if ans < tmp {
                    ans = tmp
                }
                break
            }
        }
        top++
        stack[top]=a[i]
    }

    stack[1]=a[n-1]
    top = 1
    for i := n-2; i>=0;i-- {
        for top>0 {
            // 如果栈顶元素小于当前值
            if stack[top]<a[i] {
                top--
            }else{
                // 维护最大值
                tmp := a[i]^stack[top]
                if ans < tmp {
                    ans=tmp
                }
                break
            }
        }
        top++
        stack[top]=a[i]
    }

    return ans;
}