难度: Medium
给你一个整数数组 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 * 1050 <= nums[i] <= 231 - 1运行时间: 91 ms
内存: 41.9 MB
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
h = max(nums).bit_length()-1
ans = 0
mask = 0
for i in range(h, -1, -1):
mask |= 1 << i
seen = set()
newAns = ans | 1 << i
for num in nums:
num &= mask
if (newAns ^ num) in seen:
ans = newAns
break
seen.add(num)
return ans
该题解采用了二进制前缀树（Trie）的思想。从最高位开始，逐位尝试将最大异或值 ans 的当前位设为 1。对于每一位，我们维护一个集合 seen，存储之前遍历过的数在当前位及更高位上的部分。如果能找到一个数，使得它与 newAns 的异或结果在 seen 中，说明 newAns 是可以达到的，我们将 ans 更新为 newAns。
时间复杂度: O(nL)
空间复杂度: O(n)
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
# 求最大数的二进制位数
h = max(nums).bit_length()-1
ans = 0
mask = 0
# 从最高位开始遍历
for i in range(h, -1, -1):
# 更新掩码，将当前位设为 1
mask |= 1 << i
seen = set()
# 尝试将 ans 的当前位设为 1
newAns = ans | 1 << i
for num in nums:
# 将 num 的高位部分加入 seen
num &= mask
# 如果 newAns 可以通过异或运算得到，更新 ans
if (newAns ^ num) in seen:
ans = newAns
break
seen.add(num)
return ans
从最高位开始而不是从最低位开始的原因在于最高位对最终的异或结果影响最大。异或操作中，最高位的不同会导致结果的变化最为明显，因此，为了确保得到可能的最大异或值，我们优先考虑最高位，尝试在每一位上获取最大的值。这种方式确保了从最重要的位开始分析，逐步向下确认每一位的最优选择。
掩码 `mask` 的使用是为了在处理每一位时，能够将数字的高位至当前遍历位之间的部分隔离出来。通过逐步增加掩码的位数（即通过或操作加上当前位的二进制1），我们能够保证只考虑到当前位及其以上位的部分。这样做使得我们可以集中在当前位的异或操作上，而不受低位的干扰，有助于精确地评估当前位能否通过异或达成目标值 newAns。
在题解中，`seen` 集合存储的是 `num & mask` 的结果，意味着它仅存储了每个数的高位到当前位的部分。这样的设计有助于我们在检查是否可以通过当前的 num 和已经存在的前缀达到 newAns 时，仅关注对结果影响最大的那部分数字。如果在 `seen` 中可以找到一个数，使得它与 newAns 的异或结果也存在于 `seen` 中，那么这个 newAns 是可行的。这种方法通过逐步构建可能的最大值，每一步都确保可以通过已有的数的组合达到这一目标，从而寻找到整体的最大异或值。