Hard
题目描述
给你一个非负整数数组 nums 和一个整数 k。
你必须选择 nums 的一个子数组，使得其最大元素和最小元素之间的差值最多为 k。该子数组的值是子数组中所有元素的按位异或。
返回所选子数组的最大可能值。
示例 1：
输入：nums = [5,4,5,6], k = 2
输出：7
解释：
选择子数组 [5, 4, 5, 6]。
其最大和最小元素之间的差值是 6 - 4 = 2 <= k。
值为 4 XOR 5 XOR 6 = 7。
示例 2：
输入：nums = [5,4,5,6], k = 1
输出：6
解释：
选择子数组 [6]。
其最大和最小元素之间的差值是 6 - 6 = 0 <= k。
值为 6。
提示：
1 <= nums.length <= 4 * 10^40 <= nums[i] < 2^150 <= k < 2^15
解题思路
这道题需要找到一个子数组，使得其最大值和最小值的差不超过 k，并且该子数组的异或值最大。
核心思路：
滑动窗口维护有效范围：使用双指针技术，维护一个窗口
[left, right]，确保窗口内最大值和最小值的差不超过 k。可以使用单调栈或有序集合来高效维护区间最值。前缀异或 + 字典树优化查询：对于每个有效的右端点 r，我们需要在所有有效的左端点 l 中找到使得
prefix[r+1] ^ prefix[l]最大的 l。这里prefix[i] = nums[0] ^ nums[1] ^ ... ^ nums[i-1]。字典树维护前缀异或：将有效的前缀异或值插入字典树中，每个节点维护计数以支持删除操作。对于查询，在字典树中贪心地选择与当前前缀异或值异或后结果最大的路径。
算法流程：
- 使用滑动窗口维护满足条件的区间
- 当右端点扩展时，将对应的前缀异或值加入字典树
- 当窗口不满足条件时，移动左端点并从字典树中删除对应前缀
- 对每个位置查询字典树获得最大异或值
推荐解法： 滑动窗口 + 字典树，时间复杂度 O(n log max_val)，空间复杂度 O(n log max_val)。
代码实现
class Solution {
public:
struct TrieNode {
TrieNode* children[2];
int count;
TrieNode() : count(0) {
children[0] = children[1] = nullptr;
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(int num) {
TrieNode* node = root;
for (int i = 14; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!node->children[bit]) {
node->children[bit] = new TrieNode();
}
node = node->children[bit];
node->count++;
}
}
void remove(int num) {
TrieNode* node = root;
for (int i = 14; i >= 0; i--) {
int bit = (num >> i) & 1;
node = node->children[bit];
node->count--;
}
}
int maxXor(int num) {
TrieNode* node = root;
int result = 0;
for (int i = 14; i >= 0; i--) {
int bit = (num >> i) & 1;
int wantBit = 1 - bit;
if (node->children[wantBit] && node->children[wantBit]->count > 0) {
result |= (1 << i);
node = node->children[wantBit];
} else {
node = node->children[bit];
}
}
return result;
}
};
int maxXor(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] ^ nums[i];
}
Trie trie;
int left = 0, maxResult = 0;
for (int right = 0; right < n; right++) {
while (left <= right) {
int minVal = *min_element(nums.begin() + left, nums.begin() + right + 1);
int maxVal = *max_element(nums.begin() + left, nums.begin() + right + 1);
if (maxVal - minVal <= k) break;
left++;
}
for (int i = left; i <= right; i++) {
trie.insert(prefix[i]);
}
maxResult = max(maxResult, trie.maxXor(prefix[right + 1]));
// Clear trie for next iteration
trie = Trie();
}
return maxResult;
}
};
class Solution:
def maxXor(self, nums: list[int], k: int) -> int:
class TrieNode:
def __init__(self):
self.children = {}
self.count = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, num):
node = self.root
for i in range(14, -1, -1):
bit = (num >> i) & 1
if bit not in node.children:
node.children[bit] = TrieNode()
node = node.children[bit]
node.count += 1
def remove(self, num):
node = self.root
for i in range(14, -1, -1):
bit = (num >> i) & 1
node = node.children[bit]
node.count -= 1
def max_xor(self, num):
node = self.root
result = 0
for i in range(14, -1, -1):
bit = (num >> i) & 1
want_bit = 1 - bit
if want_bit in node.children and node.children[want_bit].count > 0:
result |= (1 << i)
node = node.children[want_bit]
else:
node = node.children[bit]
return result
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] ^ nums[i]
trie = Trie()
left = 0
max_result = 0
for right in range(n):
while left <= right:
min_val = min(nums[left:right + 1])
max_val = max(nums[left:right + 1])
if max_val - min_val <= k:
break
left += 1
for i in range(left, right + 1):
trie.insert(prefix[i])
max_result = max(max_result, trie.max_xor(prefix[right + 1]))
# Clear trie for next iteration
trie = Trie()
return max_result
public class Solution {
public class TrieNode {
public TrieNode[] Children = new TrieNode[2];
public int Count = 0;
}
public class Trie {
private TrieNode root = new TrieNode();
public void Insert(int num) {
var node = root;
for (int i = 14; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.Children[bit] == null) {
node.Children[bit] = new TrieNode();
}
node = node.Children[bit];
node.Count++;
}
}
public void Remove(int num) {
var node = root;
for (int i = 14; i >= 0; i--) {
int bit = (num >> i) & 1;
node = node.Children[bit];
node.Count--;
}
}
public int MaxXor(int num) {
var node = root;
int result = 0;
for (int i = 14; i >= 0; i--) {
int bit = (num >> i) & 1;
int wantBit = 1 - bit;
if (node.Children[wantBit] != null && node.Children[wantBit].Count > 0) {
result |= (1 << i);
node = node.Children[wantBit];
} else {
node = node.Children[bit];
}
}
return result;
}
}
public int MaxXor(int[] nums, int k) {
int n = nums.Length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] ^ nums[i];
}
var trie = new Trie();
int left = 0, maxResult = 0;
for (int right = 0; right < n; right++) {
while (left <= right) {
int minVal = nums[left..right+1].Min();
int maxVal = nums[left..right+1].Max();
if (maxVal - minVal <= k) break;
left++;
}
for (int i = left; i <= right; i++) {
trie.Insert(prefix[i]);
}
maxResult = Math.Max(maxResult, trie.MaxXor(prefix[right + 1]));
// Clear trie for next iteration
trie = new Trie();
}
return maxResult;
}
}
var maxXor = function(nums, k) {
class TrieNode {
constructor() {
this.children = new Array(2);
this.count = 0;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(num) {
let node = this.root;
for (let i = 14; i >= 0; i--) {
const bit = (num >> i) & 1;
if (!node.children[bit]) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
node.count++;
}
}
remove(num) {
let node = this.root;
for (let i = 14; i >= 0; i--) {
const bit = (num >> i) & 1;
node = node.children[bit];
node.count--;
}
}
maxXor(num) {
let node = this.root;
let result = 0;
for (let i = 14; i >= 0; i--) {
const bit = (num >> i) & 1;
const wantBit = 1 - bit;
if (node.children[wantBit] && node.children[wantBit].count > 0) {
result |= (1 << i);
node = node.children[wantBit];
} else {
node = node.children[bit];
}
}
return result;
}
}
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] ^ nums[i];
}
let trie = new Trie();
let left = 0, maxResult = 0;
for (let right = 0; right < n; right++) {
while (left <= right) {
const subarray = nums.slice(left, right + 1);
const minVal = Math.min(...subarray);
const maxVal = Math.max(...subarray);
if (maxVal - minVal <= k) break;
left++;
}
for (let i = left; i <= right; i++) {
trie.insert(prefix[i]);
}
maxResult = Math.max(maxResult, trie.maxXor(prefix[right + 1]));
// Clear trie for next iteration
trie = new Trie();
}
return maxResult;
};
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 滑动窗口 + 字典树 | O(n² log V) | O(n log V) |
其中 n 是数组长度，V 是数组中的最大值（约为 2^15）。由于每次重建字典树导致时间复杂度较高，可以进一步优化为 O(n log V)。