2026-06-17：最大子数组异或值。用go语言，给定一个非负整数数组 nums 和一个整数 k。你需要从中挑选任意一个连续非空子数组，使得该子数

2026-06-17：最大子数组异或值。用go语言，给定一个非负整数数组 nums 和一个整数 k。你需要从中挑选任意一个连续非空子数组，使得该子数组内最大值与最小值的差不超过 k。在满足这一条件的所有子数组中，计算每个子数组的按位异或结果（即把子数组所有元素依次做 XOR），并返回这些异或结果里最大的那一个值。

1 <= nums.length <= 40000。

0 <= nums[i] < 32768。

0 <= k < 32768。

输入： nums = [5,4,5,6], k = 2。

输出： 7。

解释：

选择子数组 [5, 4, 5, 6]。

该子数组中最大值与最小值的差为 6 – 4 = 2 <= k。

该子数组的值为 4 XOR 5 XOR 6 = 7。

题目来自力扣3845。

整体算法分步详细拆解

题目需求梳理：找出所有连续子数组，满足子数组内最大值−最小值 ≤ k；在所有合法子数组的异或值中，求最大异或。
数组长度上限4e4，暴力枚举所有子数组会超时，代码采用滑动窗口（单调队列）+ 二进制贪心试填 + 前缀异或三段式解法，整体分为两大核心阶段：

第一阶段：单调队列滑动窗口，预处理每个右端点对应的最小合法左边界 lefts[] 前置概念

1. 前缀异或数组sum：sum[0]=0，sum[i] = nums[0]^nums[1]^...^nums[i-1]
任意子数组nums[l ... r]的异或值 =sum[r+1] ^ sum[l]，这是异或子数组标准转换公式。

2. 滑动窗口约束：窗口[left, right]满足区间最大值−最小值 ≤ k；若差值超过k，窗口左边界必须右移缩小。

3. 两个单调队列：

•minQ：单调递增队列，存储下标，队首是当前窗口最小值下标；

•maxQ：单调递减队列，存储下标，队首是当前窗口最大值下标。

步骤1：遍历每个右端点 right（逐个把nums[right]加入窗口）

1. 更新前缀异或：sum[right+1] = sum[right] ^ nums[right]，同步记录数组全局最大值mx，用于后续二进制位长度计算。

2. 元素入单调队列维护单调性：

• 最小队列minQ：队尾所有 ≥ 当前值nums[right] 的下标全部弹出，再把right追加到队尾。保证队列内对应数值从小到大，队首永远是窗口最小值。

• 最大队列maxQ：队尾所有 ≤ 当前值nums[right] 的下标全部弹出，再把right追加到队尾。保证队列内对应数值从大到小，队首永远是窗口最大值。

3. 收缩左边界，保证窗口合法：
循环判断当前窗口最大值（nums[maxQ[0]]）− 当前窗口最小值（nums[minQ[0]]）> k：

• 左边界left自增1；

• 检查两个队列队首下标是否小于新left，若小于说明队首元素已滑出窗口，弹出队首；
循环直到窗口最值差 ≤ k，此时[left, right]是以right为右端点、左边界最小的合法窗口，所有左端点在 [left, right] 的子数组nums[l…right] 全部合法。

4. 记录边界：lefts[right] = left，含义：当子数组右端是right时，合法子数组的左端点l必须 ≥ lefts[right]。

第一阶段输出结果

数组 lefts，长度等于nums长度，每个位置存对应右端点的最小合法左边界；前缀异或数组sum完整构建完成。

第二阶段：二进制高位贪心试填，求最大合法前缀异或差值（最大子数组异或） 核心思路

异或最大值优先保证高位尽可能为1，从最高二进制位到最低位逐位尝试：

1. 假设当前已确定高位结果ans，当前处理第i位，尝试把这一位设为1，得到候选值newAns = ans | (1<

2. 遍历所有右端点right，查询是否存在前缀异或sum[l]，满足：

• l ≥ lefts[right]（保证子数组nums[l…right]合法）

• sum[right+1] ^ sum[l] = newAns（若存在，说明能构造出高位为1的更大异或值）

3. 若存在满足条件的sum[l]，则ans第i位固定为1；否则保持0，继续处理下一位。

前置准备

1. 由全局最大值mx算出二进制总位数width = bits.Len(uint(mx))，代表最多需要处理多少个二进制位；

2. 数组last，作用：记录每种前缀异或值s最后一次出现的下标位置，大小为 2^width，初始值-1。

逐位贪心完整流程（从最高位i向下遍历到0）

1. 重置last数组：清空所有记录，仅初始化 last[0] = 0，对应前缀异或sum[0]=0出现在下标0。

2. ans整体左移一位，预留当前第i位的填充位置；生成候选值 newAns = ans | 1（尝试当前位填1）。

3. 再次遍历全部右端点right：

• 截取sum[right+1]的高位s：s = sum[right+1] >> i，舍弃i位以下低位，只保留高位做匹配；

• 匹配判断：查询 last[newAns ^ s]，该值代表能和s异或得到newAns的前缀异或值上次出现的下标；
若下标 ≥ lefts[right]，说明存在合法左边界l，子数组异或能达到newAns，直接把ans更新为newAns，跳出当前right循环，当前位确定为1；

• 若不满足匹配条件，更新last[s] = right+1，记录当前前缀异或s的最新下标，供后续right匹配使用。

4. 循环处理完所有二进制位后，ans即为全局最大合法子数组异或值。

样例 nums=[5,4,5,6], k=2 流程简要演示 阶段1滑动窗口预处理

逐个right=0,1,2,3计算lefts：

1. right=0（值5）：窗口[0,0]，最值差0≤2 → lefts[0]=0

2. right=1（值4）：窗口[0,1]，max5-min4=1≤2 → lefts[1]=0

3. right=2（值5）：窗口[0,2]，max5-min4=1≤2 → lefts[2]=0

4. right=3（值6）：窗口[0,3]，max6-min4=2≤2 → lefts[3]=0
最终lefts=[0,0,0,0]，所有右端点的合法左边界都从0开始，整个数组是合法窗口。
前缀异或sum=[0,5,1,4,2]

阶段2二进制贪心求最大异或

mx=6，二进制110，width=3，处理i=2、1、0三位：

1. 最高位i=2（4的位）：尝试ans第2位为1，遍历所有前缀异或，存在匹配，ans=4；

2. i=1（2的位）：尝试叠加2，newAns=6，存在匹配，ans=6；

3. i=0（1的位）：尝试叠加1，newAns=7，存在合法前缀匹配，ans=7；
最终返回7，与样例输出一致。

时间复杂度分析 1. 第一阶段：单调滑动窗口 O(n)

n = nums长度（上限4e4）

• 每个元素只会入队、出队minQ、maxQ各1次，队列操作总次数不超过2n；

• 外层right循环n次，内层收缩left循环整体最多执行n次，无嵌套平方操作；
整体线性 O(n)。

2. 第二阶段：二进制贪心 O(width × n)

• width：nums[i] < 32768 = 2^15，因此width固定最大15位；

• 外层二进制循环：固定最多15次；

• 内层每次完整遍历数组n个right，单层循环O(n)；
该阶段总复杂度 O(15×n) = O(n)。

总时间复杂度

两段相加：O(n) + O(15n) =O(n)，n≤4e4，计算量极低，不会超时。

额外空间复杂度（不计输入nums）

1. lefts数组：长度n → O(n)

2. sum前缀异或数组：长度n+1 → O(n)

3. minQ、maxQ单调队列：最多存储n个下标，合计O(n)

4. last数组：大小 2^width，width最大15 → 2^15=32768，常数空间O(1)

总额外空间复杂度：O(n)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math/bits"
)

 func maxXor(nums []int, k int) (ans int) {
    // 预处理：当窗口右端点在 right 时，窗口左端点在 lefts[right]
    // 顺带算出前缀异或和、nums 的最大值
    n := len(nums)
    lefts := make([]int, n)
    sum := make([]int, len(nums)+1)
    mx := 0
    var minQ, maxQ []int
    left := 0
    for right, x := range nums {
        sum[right+1] = sum[right] ^ x
        mx = max(mx, x)

         // 1. 入
        forlen(minQ) > 0 && x <= nums[minQ[len(minQ)-1]] {
            minQ = minQ[:len(minQ)-1]
        }
        minQ = append(minQ, right)

         forlen(maxQ) > 0 && x >= nums[maxQ[len(maxQ)-1]] {
            maxQ = maxQ[:len(maxQ)-1]
        }
        maxQ = append(maxQ, right)

         // 2. 出
        for nums[maxQ[0]]-nums[minQ[0]] > k {
            left++
            if minQ[0] < left {
                minQ = minQ[1:]
            }
            if maxQ[0] < left {
                maxQ = maxQ[1:]
            }
        }

         // 3. 记录此时的 left
        lefts[right] = left
    }

     // 试填法
    width := bits.Len(uint(mx))
    last := make([]int, 1< 
 
 
 
      
 for 
  i := width -  
 1 
 ; i >=  
 0 
 ; i-- { 
 
 
          
 for 
  j :=  
 range 
 1 
  << (width - i) { 
 
 
             last[j] =  
 -1 
 
 
         } 
 
 
         last[ 
 0 
 ] =  
 0 
 // sum[0] = 0 的位置是 0 
 
 
         ans <<=  
 1 
 
 
         newAns := ans |  
 1 
 
 
          
 for 
  right, l :=  
 range 
  lefts { 
 
 
             s := sum[right+ 
 1 
 ] >> i    
 // 去掉低位，只看高位 
 
 
              
 if 
  last[newAns^s] >= l {  
 // newAns^s 存在，且在窗口内 
 
 
                 ans = newAns  
 // 最终答案第 i 位填 1 
 
 
                  
 break 
 
 
             } 
 
 
             last[s] = right +  
 1 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
 
 
 } 
 
 
 
 
 func main() 
  { 
 
 
     nums := [] 
 int 
 { 
 5 
 ,  
 4 
 ,  
 5 
 ,  
 6 
 } 
 
 
     k :=  
 2 
 
 
     result := maxXor(nums, k) 
 
 
     fmt.Println(result) 
 
 
 } 
 
 
 

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def maxXor(nums: List[int], k: int) -> int:
    n = len(nums)
    lefts = [0] * n
    prefix_sum = [0] * (n + 1)
    mx = 0
    # 单调队列求窗口左端点
    min_q = []
    max_q = []
    left = 0
    for right, x in enumerate(nums):
        prefix_sum[right + 1] = prefix_sum[right] ^ x
        mx = max(mx, x)
        # 入队
        while min_q and x <= nums[min_q[-1]]:
            min_q.pop()
        min_q.append(right)
        while max_q and x >= nums[max_q[-1]]:
            max_q.pop()
        max_q.append(right)
        # 出队
        while nums[max_q[0]] - nums[min_q[0]] > k:
            left += 1
            if min_q[0] < left:
                min_q.pop(0)
            if max_q[0] < left:
                max_q.pop(0)
        # 记录此时的左端点
        lefts[right] = left
    # 试填法求最大异或值
    width = mx.bit_length()
    ans = 0
    for i in range(width - 1, -1, -1):
        # 初始化 last 数组
        last = [-1] * (1 << (width - i))
        last[0] = 0  # prefix_sum[0] = 0 的位置是 0
        ans <<= 1
        new_ans = ans | 1
        found = False
        for right, l in enumerate(lefts):
            s = prefix_sum[right + 1] >> i  # 去掉低位，只看高位
            if last[new_ans ^ s] >= l:  # new_ans^s 存在，且在窗口内
                ans = new_ans  # 最终答案第 i 位填 1
                found = True
                break
            last[s] = right + 1
        if not found:
            # 如果没找到，ans 保持原样（第 i 位为 0）
            pass
    return ans

 def main():
    nums = [5, 4, 5, 6]
    k = 2
    result = maxXor(nums, k)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

    


 using namespace std;

 int maxXor(vector& nums, int k) {
    int n = nums.size();
    vector lefts(n);
    vector prefix_sum(n + 1, 0);
    int mx = 0;

     // 单调队列求窗口左端点
    deque min_q, max_q;
    int left = 0;

     for (int right = 0; right < n; right++) {
        int x = nums[right];
        prefix_sum[right + 1] = prefix_sum[right] ^ x;
        mx = max(mx, x);

         // 入队
        while (!min_q.empty() && x <= nums[min_q.back()]) {
            min_q.pop_back();
        }
        min_q.push_back(right);

         while (!max_q.empty() && x >= nums[max_q.back()]) {
            max_q.pop_back();
        }
        max_q.push_back(right);

         // 出队
        while (nums[max_q.front()] - nums[min_q.front()] > k) {
            left++;
            if (min_q.front() < left) {
                min_q.pop_front();
            }
            if (max_q.front() < left) {
                max_q.pop_front();
            }
        }

         // 记录此时的左端点
        lefts[right] = left;
    }

     // 试填法求最大异或值
    int width = 0;
    int temp = mx;
    while (temp > 0) {
        width++;
        temp >>= 1;
    }
    if (width == 0) width = 1; // 处理 mx = 0 的情况

     int ans = 0;

     for (int i = width - 1; i >= 0; i--) {
        // 初始化 last 数组
        int last_size = 1 << (width - i);
        vector last(last_size, -1);
        last[0] = 0; // prefix_sum[0] = 0 的位置是 0

         ans <<= 1;
        int new_ans = ans | 1;
        bool found = false;

         for (int right = 0; right < n; right++) {
            int l = lefts[right];
            int s = prefix_sum[right + 1] >> i; // 去掉低位，只看高位

             // 检查 new_ans ^ s 是否存在，且在窗口内
            if (last[new_ans ^ s] >= l) {
                ans = new_ans; // 最终答案第 i 位填 1
                found = true;
                break;
            }
            last[s] = right + 1;
        }

         // 如果没找到，ans 保持原样（第 i 位为 0）
    }

     return ans;
}

 int main() {
    vector nums = {5, 4, 5, 6};
    int k = 2;
    int result = maxXor(nums, k);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。