2026世界杯中国线上平台
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临了一次出现的下标位置，大小为 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；
2026世界杯中国压球官网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科普著作、器具评测、普及后果的隐秘以及行业知悉。
迎接怜惜“福大大架构师逐日一题”2026世界杯中国线上平台，发音讯可获取口试贵府，让AI助力您的改日发展。
