Medium

题目描述

给你一个长度为 n 的 0 索引 数组 nums，数组由非负整数组成。对于 0 到 n - 1 之间的每个索引 i，你必须确定 nums 中从 i 开始（包括 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 开始，产生最大按位或的最短子数组是 [1,0,2]。
- 从索引 1 开始，产生最大按位或的最短子数组是 [0,2,1]。
- 从索引 2 开始，产生最大按位或的最短子数组是 [2,1]。
- 从索引 3 开始，产生最大按位或的最短子数组是 [1,3]。
- 从索引 4 开始，产生最大按位或的最短子数组是 [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

解题思路

这道题的关键在于理解按位或运算的性质：一旦某个位被设置为1，它就不会再变回0。因此，随着子数组长度的增加，按位或的结果只会保持不变或增大。

核心思路：

  1. 全局最大值：首先计算整个数组的按位或结果，这就是任意起始位置能达到的最大按位或值。

  2. 逆向思考：对于每个位置i，我们需要找到从i开始的最短子数组，使其按位或等于全局最大值。关键观察是：从右往左处理更高效。

  3. 位追踪法：对于每个二进制位，我们记录从右侧最近出现该位为1的位置。当处理位置i时，我们需要确保子数组包含所有必要的位，因此子数组长度至少要延伸到最远的必需位置。

算法步骤：

  • 从右往左遍历数组
  • 对于每个位置，维护一个数组记录每个二进制位最近出现的位置
  • 更新当前位置对应的位信息
  • 计算需要覆盖的最远位置，确定最小子数组长度

这种方法的时间复杂度为O(n·log(max(nums)))，空间复杂度为O(log(max(nums)))，是一个高效的解决方案。

代码实现

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        vector<int> lastPos(32, -1); // 记录每个位最后出现的位置
        
        // 从右向左处理
        for (int i = n - 1; i >= 0; i--) {
            // 更新当前数字对应的位
            for (int bit = 0; bit < 32; bit++) {
                if ((nums[i] >> bit) & 1) {
                    lastPos[bit] = i;
                }
            }
            
            // 找到需要覆盖的最远位置
            int maxPos = i;
            for (int bit = 0; bit < 32; bit++) {
                if (lastPos[bit] != -1) {
                    maxPos = max(maxPos, lastPos[bit]);
                }
            }
            
            result[i] = maxPos - i + 1;
        }
        
        return result;
    }
};

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        last_pos = [-1] * 32  # 记录每个位最后出现的位置
        
        # 从右向左处理
        for i in range(n - 1, -1, -1):
            # 更新当前数字对应的位
            for bit in range(32):
                if (nums[i] >> bit) & 1:
                    last_pos[bit] = i
            
            # 找到需要覆盖的最远位置
            max_pos = i
            for bit in range(32):
                if last_pos[bit] != -1:
                    max_pos = max(max_pos, last_pos[bit])
            
            result[i] = max_pos - i + 1
        
        return result

public class Solution {
    public int[] SmallestSubarrays(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        int[] lastPos = new int[32]; // 记录每个位最后出现的位置
        Array.Fill(lastPos, -1);
        
        // 从右向左处理
        for (int i = n - 1; i >= 0; i--) {
            // 更新当前数字对应的位
            for (int bit = 0; bit < 32; bit++) {
                if ((nums[i] >> bit & 1) == 1) {
                    lastPos[bit] = i;
                }
            }
            
            // 找到需要覆盖的最远位置
            int maxPos = i;
            for (int bit = 0; bit < 32; bit++) {
                if (lastPos[bit] != -1) {
                    maxPos = Math.Max(maxPos, lastPos[bit]);
                }
            }
            
            result[i] = maxPos - i + 1;
        }
        
        return result;
    }
}

var smallestSubarrays = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    const lastPos = new Array(32).fill(-1); // 记录每个位最后出现的位置
    
    // 从右向左处理
    for (let i = n - 1; i >= 0; i--) {
        // 更新当前数字对应的位
        for (let bit = 0; bit < 32; bit++) {
            if ((nums[i] >> bit) & 1) {
                lastPos[bit] = i;
            }
        }
        
        // 找到需要覆盖的最远位置
        let maxPos = i;
        for (let bit = 0; bit < 32; bit++) {
            if (lastPos[bit] !== -1) {
                maxPos = Math.max(maxPos, lastPos[bit]);
            }
        }
        
        result[i] = maxPos - i + 1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log(max(nums)))需要遍历数组一次，每次检查32个二进制位
空间复杂度O(log(max(nums)))需要额外数组存储每个位的最后出现位置

相关题目