问题描述

给定一个非负整数数组 nums 和一个整数 k，需要选择一个连续非空子数组，使得该子数组内最大值与最小值的差不超过 k。子数组的"值"定义为其中所有元素的按位异或（XOR）。要求返回所有合法子数组中，最大的异或值。

```
输入: nums = [5,4,5,6], k = 2
输出: 7
解释: 选择子数组 [5,4,5,6]，最大值6 - 最小值4 = 2 ≤ k，异或值 4^5^6 = 7
```

约束：nums.length ≤ 4×10^4，nums[i] < 2^15，暴力枚举所有子数组（O(n²)）不可行。

---

算法思路

本题结合了三个经典技巧：

1. 前缀异或（Prefix XOR）：子数组 [l, r] 的异或值 = prefix[r+1] ^ prefix[l]，将子数组异或问题转化为"两个前缀值的异或最大值"问题。
2. 01字典树（Binary Trie）：将所有前缀异或值按二进制位插入 Trie，查询时贪心选择相反的位，即可快速找到与当前值异或最大的前缀值。
3. 滑动窗口 + 单调队列：维护窗口内最大值和最小值，保证 max - min ≤ k。

整体流程：用右指针扩展窗口，用两个单调队列维护窗口最值。当窗口不满足 max - min ≤ k 时，移动左指针缩小窗口。每次窗口合法时，将对应的前缀异或值加入 Trie，查询当前前缀能得到的最大异或值并更新答案。

---

C语言完整实现

```c
#define MAX_NODES 600000  // n ≤ 40000，每个数15位，节点数 ≤ n * 15 + 1

typedef struct TrieNode {
    struct TrieNode* child[2];
    int count;  // 该节点被多少前缀值经过（用于删除）
} TrieNode;

TrieNode pool[MAX_NODES];
int pool_idx;

TrieNode* newNode() {
    TrieNode* node = &pool[pool_idx++];
    node->child[0] = node->child[1] = NULL;
    node->count = 0;
    return node;
}

// 插入或删除一个前缀异或值（delta = 1 插入，-1 删除）
void updateTrie(TrieNode* root, int val, int delta) {
    TrieNode* cur = root;
    for (int bit = 14; bit >= 0; bit--) {  // 2^15，所以15位（14~0）
        int b = (val >> bit) & 1;
        if (!cur->child[b]) cur->child[b] = newNode();
        cur = cur->child[b];
        cur->count += delta;
    }
}

// 查询与 val 异或最大的值
int queryMaxXor(TrieNode* root, int val) {
    TrieNode* cur = root;
    int res = 0;
    for (int bit = 14; bit >= 0; bit--) {
        int b = (val >> bit) & 1;
        int opposite = b ^ 1;
        if (cur->child[opposite] && cur->child[opposite]->count > 0) {
            res |= (1 << bit);
            cur = cur->child[opposite];
        } else {
            cur = cur->child[b];
        }
    }
    return res;
}

// 单调队列（存储下标）
int maxQ[40005], minQ[40005];
int maxHead, maxTail, minHead, minTail;

int maxXor(int* nums, int numsSize, int k) {
    pool_idx = 0;
    TrieNode* root = newNode();
    
    maxHead = maxTail = minHead = minTail = 0;
    
    int* prefix = (int*)malloc((numsSize + 1) * sizeof(int));
    prefix[0] = 0;
    for (int i = 0; i < numsSize; i++) {
        prefix[i + 1] = prefix[i] ^ nums[i];
    }
    
    int left = 0;
    int ans = 0;
    
    // 先插入 prefix[0]（对应空前缀，表示从数组开头开始的子数组）
    updateTrie(root, prefix[0], 1);
    
    for (int right = 0; right < numsSize; right++) {
        // 维护最大值单调队列（递减）
        while (maxHead < maxTail && nums[maxQ[maxTail - 1]] <= nums[right]) maxTail--;
        maxQ[maxTail++] = right;
        
        // 维护最小值单调队列（递增）
        while (minHead < minTail && nums[minQ[minTail - 1]] >= nums[right]) minTail--;
        minQ[minTail++] = right;
        
        // 如果窗口不满足 max - min ≤ k，移动左指针
        while (maxHead < maxTail && minHead < minTail && 
               nums[maxQ[maxHead]] - nums[minQ[minHead]] > k) {
            // 从 Trie 中移除 prefix[left]
            updateTrie(root, prefix[left], -1);
            left++;
            // 移除队列中已经滑出窗口的下标
            while (maxHead < maxTail && maxQ[maxHead] < left) maxHead++;
            while (minHead < minTail && minQ[minHead] < left) minHead++;
        }
        
        // 查询当前前缀 prefix[right+1] 能与 Trie 中已有前缀产生的最大异或值
        int curXor = queryMaxXor(root, prefix[right + 1]);
        if (curXor > ans) ans = curXor;
        
        // 将当前前缀插入 Trie
        updateTrie(root, prefix[right + 1], 1);
    }
    
    free(prefix);
    return ans;
}
```

---

代码说明

· Trie 节点池：用静态数组 pool 预分配内存，避免频繁 malloc，提高效率。
· count 字段：记录经过该节点的前缀值数量，支持删除操作（窗口滑动时移出左端前缀）。
· 15位遍历：因为 nums[i] < 2^15，异或值也在15位范围内，从高位（bit 14）到低位贪心。
· 单调队列：maxQ 维护窗口最大值下标（递减），minQ 维护最小值下标（递增）。窗口不满足条件时移动 left，并从 Trie 中移除对应的前缀值。
· 时间复杂度：O(n × 15)，空间复杂度 O(n × 15)。