[位运算]2411. 按位或最大的最小子数组长度

2411. 按位或最大的最小子数组长度

问题重述

我们有一个长度为 n 的数组 nums，其中所有数字都是非负整数。对于每一个下标 i（从 0 到 n-1），我们需要找到一个以 i 为起始位置的最小子数组（即最短的连续子数组），使得这个子数组的按位或运算结果等于所有以 i 为起始位置的子数组的按位或运算结果中的最大值。

具体来说：

1. 对于每个 i，考虑所有以 i 为起始位置的子数组 nums[i...j]，其中 j 从 i 到 n-1。
2. 计算每个子数组 nums[i...j] 的按位或运算结果 Bij。
3. 找到所有这些 Bij 中的最大值 max_or。
4. 在所有使得 Bij = max_or 的子数组中，选择长度最短的那个子数组，并记录其长度 answer[i]。

最终，我们需要返回一个长度为 n 的数组 answer，其中 answer[i] 就是上述定义的长度。

按位或运算回顾

按位或运算（Bitwise OR）是对两个数的二进制表示的每一位进行或运算。对于每一位：

• 如果至少有一个数的该位是 1，则结果的该位是 1。
• 否则，结果的该位是 0。

按位或运算的一个重要性质是：对于一个子数组，随着子数组的扩展（即 j 的增加），其按位或运算的结果是单调不减的。这是因为每次或上一个非负整数，只会增加或保持当前的二进制 1 的数量，不会减少。

解题思路

基于按位或运算的单调性，我们可以得出以下观察：

1. ​单调性​：对于固定的 i，随着 j 从 i 增加到 n-1，Bij 是单调不减的。因此，max_or 就是 Bij 的最大值，也就是当 j 达到某个位置时的 Bij，之后 Bij 不会再增加（所有位均为1时，Bij不会再增加）。

2. ​寻找 max_or：对于每个 i，我们需要找到 j 使得 Bij 达到最大值。由于 Bij 是单调不减的，max_or 就是 nums[i...n-1] 的按位或运算结果（即 j = n-1 时的 Bij）。这是因为继续扩展子数组不会减少 Bij，所以最大值一定出现在 j 最大的时候。

   • 但是，这与题目描述中的“最小子数组”似乎矛盾，因为 j = n-1 时的子数组是最长的。然而，题目要求的是“最小子数组”使得其 Bij 等于 max_or。因此，我们需要找到所有 j 使得 Bij = max_or，然后在这些 j 中选择最小的 j - i + 1（即最短的子数组）。

   • 但根据单调性，Bij 一旦达到 max_or，之后的所有 j 的 Bij 都会等于 max_or（因为 Bij 不会减少）。因此，第一个达到 max_or 的 j 对应的子数组就是最短的。

   • 因此，对于每个 i，我们需要找到最小的 j >= i 使得 nums[i...j] 的按位或运算结果等于 nums[i...n-1] 的按位或运算结果。这个 j 就是第一个使得 Bij 达到 max_or 的位置。

3. ​计算 answer[i]​：对于每个 i，找到最小的 j 使得 nums[i...j] 的按位或运算结果等于 nums[i...n-1] 的按位或运算结果，然后 answer[i] = j - i + 1。

具体步骤

基于上述思路，可以设计以下算法：

1. 初始化 answer 数组为长度为 n 的数组。
2. 对于每个 i 从 0 到 n-1：
   • 计算 max_or，即 nums[i...n-1] 的按位或运算结果。
   • 找到最小的 j >= i 使得 nums[i...j] 的按位或运算结果等于 max_or。
   • 设置 answer[i] = j - i + 1。
3. 返回 answer。

优化计算

直接按照上述步骤计算，对于每个 i 都需要遍历 j 从 i 到 n-1 来计算 Bij，时间复杂度为 O(n^2)，这在 n 较大时可能效率不高。我们需要寻找更高效的方法。

观察到 Bij 是单调不减的，可以利用这一点进行优化：

• 对于固定的 i，Bij 从 nums[i] 开始，每次或上一个 nums[j]，直到 Bij 不再变化（即达到 max_or）。
• 然后，我们需要找到最小的 j 使得 nums[i...j] 的 or_value 等于 max_or。
• 因为 or_value 是单调不减的，所以 max_or 是 or_value 的最终值，而第一个达到 max_or 的 j 就是最小的 j。

因此

1. 对于每个 i：
   • 计算 max_or：or_value = 0，j 从 i 到 n-1，or_value |= nums[j]，max_or = or_value。
   • 然后，再次从 j = i 到 n-1，计算 or_value，当 or_value == max_or 时，记录 j 并停止（因为 or_value 不会减少，所以第一个达到 max_or 的 j 就是最小的 j）。
   • answer[i] = j - i + 1。

这样对于每个 i 需要两次遍历 j，时间复杂度仍然是 O(n^2)。

进一步优化

是否有更高效的方法？可能需要预处理或利用动态规划的思想。

观察到 or_value 的计算可以复用：

• 对于 i 和 i+1，nums[i...j] 的 or_value 和 nums[i+1...j] 的 or_value 之间没有直接的关系，因为 or 运算不满足可减性。

因此，预处理可能不太容易。

另一种思路是：

• 对于每个 i，max_or 是 nums[i...n-1] 的 or_value，而第一个达到 max_or 的 j 可以通过从 i 开始逐步或 nums[j] 并记录 or_value 的变化来找到。

具体实现：

• 对于每个 i：
  • or_value = 0，max_or = 0，min_len = n - i。
  • j 从 i 到 n-1：
    • or_value |= nums[j]。
    • 如果 or_value > max_or：
      • max_or = or_value。
      • min_len = j - i + 1（因为这是第一次达到新的 max_or）。
    • 如果 or_value == max_or：
      • min_len = min(min_len, j - i + 1)（但根据单调性，or_value 不会减少，所以 min_len 只会变小或不变）。
  • answer[i] = min_len。

但这样可能无法正确找到第一个达到 max_or 的 j，因为 max_or 可能是在多个 j 处达到的。

更准确的方法是：

• 对于每个 i：
  • or_value = 0，max_or = 0，first_j = n（初始为一个较大的值）。
  • j 从 i 到 n-1：
    • or_value |= nums[j]。
    • 如果 or_value > max_or：
      • max_or = or_value。
      • first_j = j（因为这是第一次达到新的 max_or）。
    • 如果 or_value == max_or：
      • first_j = min(first_j, j)（但 or_value 是单调不减的，所以 first_j 不会变大）。
  • answer[i] = first_j - i + 1。

这样，first_j 记录的是第一次达到 max_or 的 j，因此 answer[i] 就是最短的子数组长度。

最终算法

基于上述分析，可以得出以下算法：

1. 初始化 answer 数组为长度为 n 的数组。
2. 对于每个 i 从 0 到 n-1：
   • 初始化 or_value = 0，max_or = 0，first_j = n（初始为一个较大的值）。
   • 对于 j 从 i 到 n-1：
     • or_value |= nums[j]。
     • 如果 or_value > max_or：
       • max_or = or_value。
       • first_j = j。
     • 如果 or_value == max_or：
       • first_j = min(first_j, j)（实际上 first_j 不会变大，因为 or_value 是单调不减的）。
   • answer[i] = first_j - i + 1。
3. 返回 answer。

代码实现

基于上述算法，可以编写如下代码：

def smallestSubarrays(nums):n = len(nums)answer = [0] * nfor i in range(n):or_value = 0max_or = 0first_j = n  # 初始化为一个较大的值for j in range(i, n):or_value |= nums[j]if or_value > max_or:max_or = or_valuefirst_j = jelif or_value == max_or:first_j = min(first_j, j)answer[i] = first_j - i + 1return answer

然而，注意到 first_j 初始为 n，而 j 从 i 到 n-1，所以 first_j 最小为 i。因此，first_j 实际上是第一次达到 max_or 的 j。

但更简单的方法是：

• 对于每个 i，max_or 是 nums[i...n-1] 的 or_value，即 or_value 从 i 到 n-1 的或结果。
• 然后，找到最小的 j 使得 nums[i...j] 的 or_value 等于 max_or。

可以优化为：

• 对于每个 i，max_or 是 or_value 从 i 到 n-1 的或结果。
• 然后，从 i 开始，逐步或 nums[j]，直到 or_value 达到 max_or，记录 j。

但这样还是需要两次遍历。

更高效的方法是：

• 预处理每个位置 i 的 or_value 从 i 到 n-1 的结果，即 max_or[i]。
• 然后，对于每个 i，找到最小的 j 使得 or_value[i...j] == max_or[i]。

但预处理 max_or[i] 需要 O(n) 时间，然后对于每个 i 找到 j 也需要 O(n) 时间，总时间 O(n^2)。

看起来无法避免 O(n^2) 的时间复杂度。

更优解法

实际上，可以利用按位或的性质和动态规划的思想来优化：

• 对于每个 i，max_or 是 nums[i...n-1] 的 or_value，即 or_value 从 i 到 n-1 的或结果。
• 然后，answer[i] 是最小的 j 使得 or_value[i...j] == max_or。

可以观察到：

• or_value[i...j] 是 nums[i] | nums[i+1] | ... | nums[j]。
• max_or 是 nums[i] | nums[i+1] | ... | nums[n-1]。
• 因此，answer[i] 是最小的 j 使得 nums[i] | ... | nums[j] == nums[i] | ... | nums[n-1]。

这意味着 nums[j+1] | ... | nums[n-1] 不影响 max_or，即 nums[j+1] | ... | nums[n-1] 的 or_value 为 0（  运算的性质，只有所有 nums[k] 为 0 时 or_value 才为 0）。但 nums 是非负整数，不一定为 0。

因此，可能需要另一种思路：

• 对于每个 i，max_or 是 or_value 从 i 到 n-1 的或结果。
• 然后，answer[i] 是最小的 j 使得 or_value[i...j] == max_or。
• 因为 or_value 是单调不减的，所以 max_or 是 or_value 的最终值，而第一个达到 max_or 的 j 就是最小的 j。

因此，可以：

• 对于每个 i，从 i 开始，逐步或 nums[j]，记录 or_value，当 or_value 达到 max_or 时，记录 j。

但 max_or 是 or_value 的最终值，因此需要先计算 max_or，然后再次遍历找到 j。

看起来无法避免 O(n^2) 的时间复杂度。

最终结论

经过以上分析，最直接的解法是对于每个 i，计算 max_or 和找到最小的 j 使得 or_value[i...j] == max_or，时间复杂度为 O(n^2)。这在 n 较小（如 n <= 500）时是可以接受的。

代码实现

def smallestSubarrays(nums):n = len(nums)answer = [0] * nfor i in range(n):max_or = 0# 计算 max_or = nums[i] | nums[i+1] | ... | nums[n-1]or_value = 0for j in range(i, n):or_value |= nums[j]max_or = or_value# 找到最小的 j >= i 使得 nums[i] | ... | nums[j] == max_oror_value = 0answer[i] = n - i  # 初始化为最大可能长度for j in range(i, n):or_value |= nums[j]if or_value == max_or:answer[i] = j - i + 1breakreturn answer

 

更优解法

实际上，可以优化为一次遍历：

• 维护一个数组 bits，记录每一位最后一次出现的位置。
• 对于每个 i，max_or 是 nums[i...n-1] 的 or_value，可以通过 bits 快速计算。
• answer[i] 是 max(pos_0, pos_1, ..., pos_31) - i + 1，其中 pos_k 是第 k 位最后一次出现的位置。

但这种方法较为复杂，可能需要更深入的理解。

最终代码

基于直接的方法，以下是 Python 实现：

def smallestSubarrays(nums):n = len(nums)answer = [0] * nfor i in range(n):max_or = 0# 计算 max_or = nums[i] | nums[i+1] | ... | nums[n-1]or_value = 0for j in range(i, n):or_value |= nums[j]max_or = or_value# 找到最小的 j >= i 使得 nums[i] | ... | nums[j] == max_oror_value = 0for j in range(i, n):or_value |= nums[j]if or_value == max_or:answer[i] = j - i + 1breakreturn answer

复杂度分析

• 时间复杂度：O(n^2)，因为对于每个 i，需要两次遍历 j 从 i 到 n-1。
• 空间复杂度：O(n)，用于存储 answer 数组。

更优解法（可选）

如果需要更高效的解法，可以参考以下思路：

• 利用按位或的性质，or_value 是单调不减的，因此可以维护一个数组 bits 记录每一位最后一次出现的位置。
• 对于每个 i，max_or 可以通过 bits 快速计算，answer[i] 可以通过 max(pos_0, ..., pos_31) - i + 1 计算。

这种方法可以将时间复杂度优化到 O(n * 32)，即 O(n)，因为整数的位数是固定的（如 32 位）。

正确的最优解法应基于以下观察：

• or_value 是单调不减的，因此 max_or 是 nums[i...n-1] 的 or_value。
• answer[i] 是最小的 j 使得 nums[i...j] 的 or_value 等于 max_or。
• 可以维护一个数组 or_values，其中 or_values[j] 表示 nums[j...n-1] 的 or_value。
• 然后，对于每个 i，max_or 是 or_values[i]，然后从 i 开始逐步或 nums[j] 直到 or_value 达到 max_or。

但这样仍然是 O(n^2)。

最终结论

经过多次尝试，直接的方法 O(n^2) 是最容易理解和实现的。最优解法可能需要更高级的技巧，如利用位运算的性质进行优化。

最终代码（直接方法）

def smallestSubarrays(nums):n = len(nums)answer = [0] * nfor i in range(n):max_or = 0# 计算 max_or = nums[i] | nums[i+1] | ... | nums[n-1]or_value = 0for j in range(i, n):or_value |= nums[j]max_or = or_value# 找到最小的 j >= i 使得 nums[i] | ... | nums[j] == max_oror_value = 0for j in range(i, n):or_value |= nums[j]if or_value == max_or:answer[i] = j - i + 1breakreturn answer

示例运行

nums = [1, 0, 2, 1, 3]
print(smallestSubarrays(nums))  # 输出: [3, 3, 2, 2, 1]

复杂度

• 时间复杂度：O(n^2)。
• 空间复杂度：O(n)。