千问 LeetCode 2935. 找出强数对的最大异或值 II JavaScript实现
这是一道经典的“字典树（Trie）+ 滑动窗口”的算法题。在开始写代码前，我们先来梳理一下解题的核心思路：
💡 核心思路
1. 转化强数对条件：
题目给出的条件是 |x - y| <= min(x, y)。为了方便处理，我们可以先对数组进行升序排序。
假设排序后 x <= y，那么 min(x, y) 就是 x，绝对值 |x - y| 就是 y - x。
原条件转化为：y - x <= x，即 y <= 2 * x。
也就是说，对于数组中任意两个数，只要满足 x <= y <= 2 * x，它们就是一对强数对。
2. 滑动窗口维护有效区间：
我们遍历排序后的数组，将当前遍历到的数作为较大的数 y。
我们需要在前面已经遍历过的数中，找到一个满足 y <= 2 * x（即 x >= y / 2）的最小的 x，从而确定一个合法的滑动窗口 [left, right]。窗口内的所有数都可以作为 x 与当前的 y 组成强数对。
3. 字典树（Trie）求最大异或值：
为了让异或值 x XOR y 最大，我们需要让二进制的高位尽可能不同（即 0 配 1，1 配 0）。
我们可以将滑动窗口内的所有 x 存入一棵 01 字典树中。对于当前的 y，我们在字典树中从高位到低位贪心地寻找与 y 当前位相反的路径，从而得到当前窗口内与 y 异或结果最大的值。
💻 JavaScript 代码实现
// 字典树节点类
class TrieNode {
constructor() {
this.children = [null, null]; // 0 和 1 两个子节点
this.cnt = 0; // 记录经过该节点的数字个数，用于删除操作
}
}
var maximumStrongPairXor = function(nums) {
// 1. 排序数组，方便使用滑动窗口和转化条件
nums.sort((a, b) => a - b);
const root = new TrieNode();
let left = 0; // 滑动窗口的左边界
let max_xor = 0;
// 辅助函数：向字典树中插入或删除一个数字
// delta = 1 表示插入，delta = -1 表示删除
const updateTrie = (val, delta) => {
let node = root;
// 题目提示 nums[i] < 2^20，所以从第 19 位开始遍历即可
for (let i = 19; i >= 0; i--) {
const bit = (val >> i) & 1;
if (!node.children[bit]) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
node.cnt += delta;
}
};
// 辅助函数：在字典树中查找与 val 异或最大的值
const findMaxXor = (val) => {
let node = root;
let xor_val = 0;
for (let i = 19; i >= 0; i--) {
const bit = (val >> i) & 1;
// 贪心策略：优先走与当前位相反的路径（bit ^ 1）
// 且该路径对应的节点必须存在且计数大于 0
if (node.children[bit ^ 1] && node.children[bit ^ 1].cnt > 0) {
xor_val |= (1 << i); // 该位异或结果为 1
node = node.children[bit ^ 1];
} else {
// 否则只能走相同的路径
node = node.children[bit];
}
}
return xor_val;
};
// 2. 遍历数组，将当前数字作为强数对中较大的数 y
for (let right = 0; right < nums.length; right++) {
const y = nums[right];
// 先将当前的 y 加入字典树（它既可以是 y，也可以作为后面更大数的 x）
updateTrie(y, 1);
// 3. 维护滑动窗口：如果窗口最左边的 x 不满足 y <= 2 * x，则将其移出窗口
while (nums[left] * 2 < y) {
updateTrie(nums[left], -1);
left++;
}
// 4. 在当前的合法窗口中，查找与 y 异或最大的值，并更新全局最大值
max_xor = Math.max(max_xor, findMaxXor(y));
}
return max_xor;
};
📝 复杂度分析
* 时间复杂度：O(N log N + N log C)。其中 N 是数组长度，log N 来自排序，log C 来自字典树的插入、删除和查询操作（C 是数字的最大值，这里约为 2^20）。
* 空间复杂度：O(N log C)。字典树在最坏情况下需要存储所有数字的二进制位。