题目

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或****运算值 。

• 换言之，令 Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。

一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,0,2,1,3] 输出：[3,3,2,2,1] 解释： 任何位置开始，最大按位或运算的结果都是 3 。

• 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
• 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
• 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
• 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
• 下标 4 处，能得到结果 3 的最短子数组是 [3] 。 所以我们返回 [3,3,2,2,1] 。

示例 2：

输入：nums = [1,2] 输出：[2,1] 解释： 下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。 下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。 所以我们返回 [2,1] 。

提示：

• n == nums.length
• 1 <= n <= 10^5
• 0 <= nums[i] <= 10^9

思路

首先，我们需要理解题目的核心要求。对于数组 nums 中的每一个起始位置 i，我们需要完成两件事：

1. 找到最大的按位或（OR）值：在所有以 i 开头的子数组 nums[i...k] (其中 i <= k < n) 中，计算它们的按位或结果，并找出其中的最大值。
2. 找到达到该最大值的最短子数组：可能有很多个以 i 开头的子数组都能得到这个最大的按位或值。我们需要在这些子数组中，找到那个长度最短的，并返回其长度。

1. 如何确定“最大的按位或值”？

按位或运算有一个非常重要的特性：单调不减性。 当你有一个数值 x，然后用它去或上另一个数 y，结果 x | y 必然大于或等于 x (x | y >= x)。这是因为 y 中为 '1' 的位，如果 x 中对应位是 '0'，就会将其变为 '1'，使得结果变大；如果 x 中对应位已经是 '1'，则保持不变。数值的二进制位只会从 0 变为 1，绝不会从 1 变为 0。

基于这个特性，对于一个固定的起始位置 i，我们考虑子数组 nums[i...j]。当我们向右扩展这个子数组，即 j 增大时，其按位或的结果 B_ij = nums[i] | nums[i+1] | ... | nums[j] 只会保持不变或者增加。

因此，对于任意一个起始位置 i，能得到的最大按位或值，必然是 i 到数组末尾所有元素的按位或结果，即 nums[i] | nums[i+1] | ... | nums[n-1]。

2. 如何寻找“最短子数组”？

现在问题转化为：对于每个 i，我们已经知道了目标最大值 max_or = nums[i] | ... | nums[n-1]。我们需要找到一个最小的 j（j >= i），使得子数组 nums[i...j] 的按位或结果恰好等于 max_or。这个最短的长度就是 j - i + 1。

一个直接的想法是双重循环：

// 伪代码
for i from 0 to n-1:
  // 1. 计算从 i 开始的最大 OR 值
  max_or = 0
  for k from i to n-1:
    max_or = max_or | nums[k]

  // 2. 寻找最短子数组
  current_or = 0
  for j from i to n-1:
    current_or = current_or | nums[j]
    if current_or == max_or:
      answer[i] = j - i + 1
      break // 找到了最短的，跳出内层循环

这个算法的时间复杂度是 O(N²)，对于 N 高达 10^5 的情况，会超时。我们需要更高效的方法。

优化思路

我们可以将问题分解成几个可以预先计算的部分，从而加速查找过程。

1.快速获取最大OR值

我们可以预先计算出所有后缀的按位或值。定义 suffix_or[i] = nums[i] | nums[i+1] | ... | nums[n-1]。 这可以通过一次从后向前的遍历来完成：

• suffix_or[n-1] = nums[n-1]
• suffix_or[i] = nums[i] | suffix_or[i+1]

这样，我们就能在 O(1) 时间内得到任何位置 i 开始的最大按位或值 suffix_or[i]。这个预计算本身需要 O(N) 时间。

第二步：高效寻找最短长度 j

现在，对于每个 i，我们要找最小的 j 使得 nums[i] | ... | nums[j] == suffix_or[i]。

这里的关键洞察是 从二进制位的角度来思考。

A | B = C 成立，当且仅当对于 C 的每一个为 '1' 的二进制位，A 或 B (或两者) 在该位上也必须是 '1'。

应用到我们的问题上： nums[i] | ... | nums[j] 要等于 suffix_or[i]，就意味着对于 suffix_or[i] 中的每一个值为 '1' 的位，在 nums[i...j] 这个子数组中，至少要有一个数在该二进制位上也为 '1'。

为了让子数组 nums[i...j] 最短，我们需要 j 尽可能小。这意味着 j 必须延伸到刚好能 "覆盖" suffix_or[i] 所有为 '1' 的位的那个位置。

换句话说，对于 suffix_or[i] 中所有为 '1' 的位 b，我们都要找到从 i 开始第一个拥有该位 b 的数 nums[k] (其中 k>=i)。所有这些 k 中的最大值，就是我们需要的最小的 j。

举例说明： 假设 i=0，suffix_or[0] 的二进制是 ...1011。

• 为了满足最低位的 '1'，我们可能在 nums[2] 找到了第一个满足的数。
• 为了满足次低位的 '1'，我们可能在 nums[0] 就找到了。
• 为了满足第3位的 '1'，我们可能在 nums[4] 才找到第一个满足的数。

那么，我们的子数组必须至少延伸到 nums[4]，即 j 最小也得是 4。因为只有这样，nums[0...4] 的按位或结果才能确保在 ...1011 这几个位上都是 '1'。

实现高效查找的数据结构

为了实现上述逻辑，我们需要一个数据结构，能快速回答：“从位置 i 开始，下一个拥有二进制位 b 的数在哪个位置？”

我们可以预计算一个二维数组 next_set_bit[i][b]，它表示在 nums 数组中，从下标 i (包含) 开始向后看，第一个在第 b 位上为 '1' 的元素的下标。 这个数组也可以通过一次从后向前的遍历来构建：

1. 创建一个数组 last_pos[30]，last_pos[b] 记录从当前位置往后看，第 b 位为 '1' 的最近下标。初始化为 n（一个无效的越界下标）。
2. 从 i = n-1 遍历到 0： a. 对于当前数字 nums[i]，更新 last_pos：对于 nums[i] 的所有为 '1' 的位 b，设置 last_pos[b] = i。 b. 此时的 last_pos 数组就包含了从 i 开始所有位的下一个出现位置。将其存入 next_set_bit[i]，即 next_set_bit[i][b] = last_pos[b]。

这个预计算的时间复杂度是 O(N * log(max(nums)))，因为 log(max(nums)) 是数字的位数（大约30）。

具体思路

1. 预计算后缀或：创建一个 suffix_or 数组。从 i = n-2 到 0 倒序遍历，计算 suffix_or[i] = nums[i] | suffix_or[i+1]。时间 O(N)。
2. 预计算下一个置位：创建一个 next_set_bit[n][30] 的二维数组。从 i = n-1 到 0 倒序遍历，计算并填充 next_set_bit[i][b]。时间 O(N * 30)。
3. 计算最终答案：
   • 创建一个 answer 数组。
   • 从 i = 0 到 n-1 正序遍历： a. 获取目标值 target_or = suffix_or[i]。 b. 初始化 required_j = i。 c. 遍历所有二进制位 b (从 0 到 29)： i. 如果 target_or 的第 b 位是 '1'： ii. 我们必须覆盖这一位。需要的最远下标是 next_set_bit[i][b]。 iii. 更新 required_j = max(required_j, next_set_bit[i][b])。 d. 循环结束后，required_j 就是能满足条件的最小 j。 e. 计算长度 answer[i] = required_j - i + 1。
   • 时间 O(N * 30)。

复杂度分析

• 时间复杂度：O(N) + O(N * 30) + O(N * 30) = O(N)，因为 30 是一个常数。这完全满足题目的时间要求。
• 空间复杂度：O(N) 用于 suffix_or，O(N * 30) 用于 next_set_bit。总空间复杂度为 O(N)。

代码实现

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        
        // 步骤 1: 预计算后缀或 (suffix_or)
        // suffix_or[i] 存储 nums[i] | nums[i+1] | ... | nums[n-1]
        std::vector<int> suffix_or(n);
        suffix_or[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suffix_or[i] = nums[i] | suffix_or[i + 1];
        }

        // 步骤 2: 预计算下一个置位的位置 (next_set_bit)
        // next_set_bit[i][b] 存储从下标 i 开始，第 b 位为 1 的最近元素的下标
        // 10^9 < 2^30，所以我们只需要处理 0 到 29 位
        std::vector<std::vector<int>> next_set_bit(n, std::vector<int>(30));
        std::vector<int> last_pos(30, n); // 初始化为 n，表示在数组内未找到

        for (int i = n - 1; i >= 0; --i) {
            // 首先更新 last_pos，记录下当前数字 nums[i] 中所有为 '1' 的位的位置
            for (int b = 0; b < 30; ++b) {
                if ((nums[i] >> b) & 1) {
                    last_pos[b] = i;
                }
            }
            // 然后用更新后的 last_pos 来填充 next_set_bit[i]
            for (int b = 0; b < 30; ++b) {
                next_set_bit[i][b] = last_pos[b];
            }
        }

        // 步骤 3: 结合预计算结果，计算最终答案
        std::vector<int> answer(n);
        for (int i = 0; i < n; ++i) {
            int target_or = suffix_or[i];
            int required_j = i; // 子数组的右边界至少是 i

            // 遍历所有可能的位
            for (int b = 0; b < 30; ++b) {
                // 如果目标或值的第 b 位是 '1'
                if ((target_or >> b) & 1) {
                    // 那么我们的子数组必须延伸到足以覆盖这一位的位置
                    // 这个位置就是 next_set_bit[i][b]
                    // 我们需要取所有这些要求位置中的最大值
                    required_j = std::max(required_j, next_set_bit[i][b]);
                }
            }
            // 长度就是 required_j - i + 1
            answer[i] = required_j - i + 1;
        }

        return answer;
    }
};

优化代码

虽然上面的三步法非常清晰，但实际上我们可以将它们合并到一个从后向前的循环中，从而减少代码量和空间（可以省掉 suffix_or 和 next_set_bit 两个辅助数组）。逻辑是相通的：在从后向前遍历到 i 时，last_pos 数组正好就代表了从 i 开始的 next_set_bit 信息，并且利用它就可以直接计算出 answer[i]。

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        std::vector<int> ans(n);
        
        // last[b] 将存储从当前位置往右看，第b位为1的最近下标
        std::vector<int> last(30, 0);

        // 从后往前遍历，一次性完成所有计算
        for (int i = n - 1; i >= 0; --i) {
            // 1. 更新 last 数组，记录 nums[i] 的位信息
            for (int b = 0; b < 30; ++b) {
                if ((nums[i] >> b) & 1) {
                    last[b] = i;
                }
            }

            // 2. 计算从 i 出发能构成的最大 OR 值所需要的最远下标 j
            // 这个最远的 j 就是 last 数组中所有出现过的位置的最大值
            int required_j = i;
            for (int b = 0; b < 30; ++b) {
                required_j = std::max(required_j, last[b]);
            }
            
            // 3. 计算并存储长度
            ans[i] = required_j - i + 1;
        }
        
        return ans;
    }
};

利用内建函数再次优化

__builtin_ctz函数可以直接从CPU级别的优化给出二进制'1'的位置，可以极大的剪枝。

// 在GCC/Clang环境下
#ifdef __GNUC__
#define BUILTIN_CTZ __builtin_ctz
#else
// 为其他编译器（如MSVC）提供回退或等效实现
// 注意：这只是一个示例，MSVC下应使用 <intrin.h> 中的 _BitScanForward
#define BUILTIN_CTZ some_fallback_ctz_function 
#endif

class Solution {
public:
        
        vector<int> smallestSubarrays(vector<int>& nums) {

        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n = nums.size();
        vector<int> ans(n);
        
        // 使用C风格数组，并放在栈上，访问速度最快
        int last[30] = {0}; 

        for (int i = n - 1; i >= 0; --i) {
            // 1. 使用CPU内建函数高效更新 last 数组
            unsigned int x = nums[i];
            while (x > 0) {
                int b = BUILTIN_CTZ(x);
                last[b] = i;
                x &= (x - 1); // 清除最低位的'1'
            }

            // 2. 找到最远的 j
            int required_j = i;
            // 这个循环因为迭代次数固定且少，编译器通常能优化得很好
            // 比如部分展开或者使用SIMD指令（如果开启了-march=native）
            for (int b = 0; b < 30; ++b) {
                required_j = max(required_j, last[b]);
            }
            
            ans[i] = required_j - i + 1;
        }
        
        return ans;
    }
};

LogTrick法

思路是，从后向前遍历，同时计算结果并维护一个状态数组（这里的 pos 数组）。

pos[bit] 的作用：存储从当前位置向右看，第 bit 位为'1'的最靠右的元素下标。

从循环 i 从 n-1 到 0 ：

1. 初始化 j = i: j 用于追踪为了构成最大“或”值，子数组 nums[i...j] 需要延伸到的最右端点。初始时，我们假设只需要 nums[i] 就够了。
2. 遍历所有位 bit:
   • 情况一：当前数字 nums[i] 的第 bit 位是 1 (else 分支)
     • pos[bit] = i;
     • 逻辑：这个 bit 的要求已经被 nums[i] 满足了。同时，我们需要更新 pos[bit] 的值为当前下标 i。这个更新非常关键，它是为了给后续的迭代（即 i-1, i-2, ...） 提供信息，告诉它们需要第 bit 位，那么在下标 i 这里就可以找到。
   • 情况二：当前数字 nums[i] 的第 bit 位是 0 (if 分支)
     • 逻辑：nums[i] 无法满足对第 bit 位的要求。为了在最终的子数组“或”和中得到这个 bit，我们必须向右寻找。
     • if (pos[bit] != -1): 我们检查之前（即从 i+1 到 n-1 的范围内）有没有记录过这个 bit 的位置。
     • j = max(j, pos[bit]);: 如果找到了（pos[bit] 不是-1），说明我们的子数组必须至少延伸到 pos[bit] 这个位置才能“收集”到这个 bit。我们用 j 来记录所有“必须延伸到”的位置中的最大值。
3. 计算结果:
   • ans[i] = j - i + 1;
   • 在检查完所有31个位之后，j 就成了那个能满足所有位要求的、最靠左的右端点。因此，最短长度就是 j - i + 1。

代码

class Solution {
public:
    /**
     * @brief 计算每个位置开始，能获得最大按位或值的最短子数组长度。
     * @param nums 非负整数数组。
     * @return 一个数组，其中 ans[i] 是从 i 开始的最短子数组的长度。
     *
     * 核心思想：采用动态规划的思路，从后向前遍历数组。
     * 维护一个状态数组 pos，其中 pos[bit] 记录了从当前位置往右看，
     * 第 `bit` 位为 '1' 的元素出现的最靠右的下标。
     * 在一次遍历中，同时利用之前（右侧）的状态计算当前结果，并更新状态以供后续（左侧）使用。
     */
    vector<int> smallestSubarrays(vector<int>& nums) {
        // 获取数组大小
        int n = nums.size();
        
        // pos 数组是核心。pos[bit] 存储第 `bit` 位为1的最靠右的下标。
        // 初始化为-1（或任何无效下标），表示尚未在右侧找到该位。
        // 使用31位因为题目中数字最大为10^9，小于2^30，31位足够覆盖。
        vector<int> pos(31, -1);
        
        // 存储最终答案的数组
        vector<int> ans(n);

        // 从后向前遍历数组
        // 这样当我们计算 ans[i] 时，所有关于 i 右侧子数组的信息（i+1 到 n-1）都已处理完毕并存储在 pos 数组中。
        for (int i = n - 1; i >= 0; --i) {
            
            // `j` 将用来确定子数组 nums[i...j] 的右边界。
            // 初始时，我们假设最短子数组只包含 nums[i] 本身。
            int j = i;

            // 遍历一个整数的所有可能位
            for (int bit = 0; bit < 31; ++bit) {
                
                // 检查当前数字 nums[i] 的第 `bit` 位是否为 0
                if (!(nums[i] & (1 << bit))) {
                    // --- 情况1: nums[i] 缺少第 `bit` 位 ---
                    
                    // 为了在子数组的“或”和中得到这一位，我们必须向右寻找。
                    // 检查 pos[bit] 是否有效，即右侧是否存在一个数拥有这一位。
                    if (pos[bit] != -1) {
                        // 如果存在，那么我们的子数组必须至少延伸到 pos[bit] 的位置。
                        // 我们需要满足所有缺失位的要求，因此 j 必须是所有这些要求位置中的最大值。
                        j = max(j, pos[bit]);
                    }
                }
                else {
                    // --- 情况2: nums[i] 拥有第 `bit` 位 ---
                    
                    // 这个 `bit` 的要求已经被 nums[i] 满足了。
                    // 最关键的一步：更新 pos[bit] 的值为当前下标 i。
                    // 这相当于向左边的元素（i-1, i-2, ...）“宣告”：
                    // "第 `bit` 位现在在下标 i 这个更近的位置就可以找到了！"
                    pos[bit] = i;
                }
            }
            
            // 在检查完所有位后，j 就是能满足所有位要求的、最靠左的右边界。
            // 因此，最短子数组的长度为 j - i + 1。
            ans[i] = j - i + 1;
        }
        
        return ans;
    }
};