offer2-67

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 231 - 1

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    class TrieNode {
        TrieNode[] next = new TrieNode[2];
        public TrieNode insert(int val) {
            TrieNode node = next[val];
            if (node == null) {
                node = new TrieNode();
                next[val] = node;
            }
            return node;
        }
    }

    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        insert(root, nums[0]);
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            // 每次元素都在与它前面所有数构造的字典树进行异或
            max = Math.max(max, maxXOR(root, nums[i]));
            insert(root, nums[i]);
        }
        return max;
    }

    public void insert(TrieNode root, int num) {
        TrieNode node = root;
        for (int i = 30; i >= 0; i--) {
            node = node.insert((num >> i) & 1);
        }
    }

    public int maxXOR(TrieNode root, int num) {
        int ans = 0;
        TrieNode node = root;
        // 对于每一个num，只需要循环31次就能找到它与其他数最大的异或值
        for (int i = 30; i >= 0; i--) {
            int choose = (num >> i) & 1;
            if (node.next[1 - choose] != null) {
                ans |= 1 << i;
                node = node.next[1 - choose];
            } else {
                node = node.next[choose];
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)