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]，轮盘游戏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++完竣代码如下：

2026世界杯比赛买输赢中国官网

#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助力您的改日发展。