开云kaiyun(中国) 2026-06-17: 最大子数组异或值。用go言语, 给定一个非负整数数组
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终末一次出现的下标位置，开云kaiyun中国手机APP下载大小为 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]，开云kaiyun(中国)该值代表能和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++;
开云2026世界杯官方授权平台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科普著述、器具评测、普及成果的秘密以及行业细察。
接待羡慕“福大大架构师逐日一题”开云kaiyun(中国)，发音书可得到口试贵寓，让AI助力您的将来发展。
备案号: