2026-06-17：最大子数组异或值。用go言语，给定一个非负整数数组 nums 和一个整数 k。你需要从中挑选苟且一个运动非空子数组，使得该子数组内最大值与最小值的差不向上 k。在兴奋这一要求的通盘子数组中，计算每个子数组的按位异或适度（即把子数组通盘元素挨次作念 XOR），并复返这些异或适度里最大的那一个值。
1
0
0
输入： nums = [5，4，5，6]， k = 2。
输出： 7。
证明：
聘用子数组 [5， 4， 5， 6]。
该子数组中最大值与最小值的差为 6 - 4 = 2
该子数组的值为 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]，兴奋：
• sum[right+1] ^ sum[l] = newAns（若存在，证明能构造出高位为1的更大异或值）
3. 若存在兴奋要求的sum[l]，则ans第i位固定为1；不然保捏0，不息搞定下一位。
前置准备
1. 由全局最大值mx算出二进制总位数width = bits.Len(uint(mx))，代表最多需要搞定些许个二进制位；
2. 数组last，作用：记载每种前缀异或值s临了一次出现的下标位置，百家乐2026世界杯中国官方下载大小为 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]，博亚体育app官方入口该值代表能和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]
• 外层二进制轮回：固定最多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
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]
minQ = minQ[1:]
}
if maxQ[0]
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 := range1
last[j] = -1
}
last[0] = 0// sum[0] = 0 的位置是 0
ans
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
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]
min_q.pop(0)
if max_q[0]
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
last[0] = 0 # prefix_sum[0] = 0 的位置是 0
ans
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++完好意思代码如下：
#include
#include
#include
#include
#include
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
int x = nums[right];
prefix_sum[right + 1] = prefix_sum[right] ^ x;
mx = max(mx， x);
// 入队
while (!min_q.empty && x
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
min_q.pop_front;
}
if (max_q.front
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
vector last(last_size， -1);
last[0] = 0; // prefix_sum[0] = 0 的位置是 0
ans
int new_ans = ans | 1;
bool found = false;
for (int right = 0; 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
return0;
}
咱们顺服东谈主工智能为泛泛东谈主提供了一种“增强器具”，并费事于共享全标的的AI常识。在这里，您不错找到最新的AI科普著述、器具评测、提高恶果的隐私以及行业瞻念察。
迎接温雅“福大大架构师逐日一题”博亚体育app官方入口，发音书可取得口试贵寓，让AI助力您的改日发展。