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

难度: Medium

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

换言之，令 B_ij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(B_ik) ，其中 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⁵
0 <= nums[i] <= 10⁹

Submission

运行时间: 174 ms

内存: 27.6 MB

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        ans=[0]*(len(nums))
        for i,x in enumerate(nums):
            ans[i]=1
            for j in range(i-1,-1,-1):
                if nums[j]|x==nums[j]:
                    break
                nums[j]|=x
                ans[j]=i-j+1
        return ans

Explain

该题解使用了从左向右遍历数组的方式，并且使用了单次遍历的贪心算法来处理每个元素。对于每个元素i，初始化ans[i]=1，意味着最短子数组至少包含自身。然后逆向遍历之前的元素，更新它们的按位或结果和最小子数组长度。如果前面的元素j通过与当前元素i的按位或不再改变（即nums[j] | x == nums[j]），则停止更新，因为进一步的按位或不会得到更大的值。如果发生改变，则更新nums[j]并且重新计算最短长度。这样做是基于这样的假设：如果一个元素需要扩展它的子数组边界来包含之后的元素，那么一定是因为新加入的元素提供了一个新的比特位，使得按位或的结果增大。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        ans = [0] * (len(nums))  # 初始化答案数组
        for i, x in enumerate(nums):  # 遍历每个元素
            ans[i] = 1  # 每个元素至少包含自身
            for j in range(i - 1, -1, -1):  # 逆向检查之前的元素
                if nums[j] | x == nums[j]:  # 如果按位或结果未改变，停止更新
                    break
                nums[j] |= x  # 更新前面元素的按位或结果
                ans[j] = i - j + 1  # 更新最短子数组长度
        return ans  # 返回结果

Explore

这种停止更新的条件是基于按位或操作的性质。当发现 `nums[j] | x == nums[j]` 时，意味着x中不存在任何新的比特位能够使nums[j]的按位或结果得到改变。因此，在这种情况下，继续加入后续的元素也不会影响当前的按位或结果，所以可以安全地停止更新。不存在需要继续扩展子数组以确保获取到更大按位或结果的情况，因为所有后续元素的包含都不会改变当前的按位或值。

算法中更新最短子数组长度为 `i - j + 1` 是指在当前元素i和检查到的元素j之间的最短距离。这并不意味着每次都重新计算从i到j所有子数组的按位或结果，而是通过连续更新前面元素的按位或结果来避免重复计算。具体来说，每个元素j在被i影响时就地更新其按位或结果。这种方法提高了效率，因为它避免了对每个子数组进行独立的按位或操作，而是利用了前一个元素的按位或结果作为基础进行增量更新。

贪心策略在这个问题中的应用是每次尽可能地缩小子数组的长度，直到找到一个最小的范围，使得子数组内元素的按位或值达到当前能达到的最大值。通过从当前元素向前检查，并在不再增加新的比特位时停止，这个方法确保了在达到最大按位或结果的同时，子数组长度保持最短。这种策略是有效的，因为它总是试图在最早的时刻停止扩展子数组长度，从而确保长度尽可能小，同时通过不断更新按位或结果，保证了按位或值是最大的。

在所有数字为0的特殊情况下，按位或的结果始终为0。算法在这种情况下依然可以正确执行，因为每个元素与0的按位或结果还是0，内层循环会在第一次检查时就终止（因为0 | 0 = 0），从而将每个元素的子数组长度设为1。这种情况下算法效率很高，因为每个元素都不需要进行多余的按位或计算，直接确定其子数组长度为1。