这是一道经典的“字典树(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)。字典树在最坏情况下需要存储所有数字的二进制位。