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

Table of Contents

LeetCode-2411 按位或最大的最小子数组长度 #

Solution 1 #

按位或运算是不减的. 对于 $j < i$ , 如果 $nums[j] | nums[i] == nums[j]$ , 说明之前的运算到 $j$ 即可, 否则需要更新到 $i$ . 将 $nums[j]$ 更新为 $nums[j] | nums[i]$ , 因为之后的操作需要重复计算这一部分.

代码如下:

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0 for _ in range(n)]
        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