leetcode3097.或值至少为 K 的最短子数组 II

univerexplorer2025-01-172025-01-19

3097. 或值至少为 K 的最短子数组 II

中等（LogTrick）

给你一个非负整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值至少为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

输入： nums = [1,2,3], k = 2

输出： 1

解释：

子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：

输入： nums = [2,1,8], k = 10

输出： 3

解释：

子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。

示例 3：

输入： nums = [1,2], k = 0

输出： 1

解释：

子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

代码一：暴力枚举

超出时间限制 714 / 718 个通过的测试用例

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = +inf
        for i in range(len(nums)):
            temp = nums[i]
            if temp >= k:
                return 1
            for j in range(i+1,len(nums)):
                temp |= nums[j]
                if temp >= k:
                    ans = min(ans,j-i+1)
                    break
        return ans if ans != +inf else -1

思路：

暴力枚举所有的子数组，找到其中满足或值大于等于 k 的最短子数组。

代码二：暴力优化

超出时间限制 717 / 718 个通过的测试用例

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = +inf
        res = 0
        for i,j in enumerate(nums):
            if j >= k:
                return 1
            res |= j
            if res >= k:
                res = j
                for m in range(i-1,-1,-1):
                    res |= nums[m]
                    if res >= k:
                        ans = min(ans,i-m+1)
                        break
        return ans if ans != +inf else -1

思路：

从后往前排查子数组。（ps：细想好像也没什么区别，但是为什么能多通过3个测试用例？会不会是数据使然，从后往前更容易满足条件）

代码三：灵神思路（LogTrick前版）

超出时间限制 714 / 718 个通过的测试用例

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = +inf
        for i,j in enumerate(nums):
            if j >= k:
                return 1
            for m in range(i-1,-1,-1):
                nums[m] |= nums[i]
                if nums[m] >= k:
                    ans = min(ans,i-m+1)
                    break
        return ans if ans != +inf else -1

思路：

还是从后往前的思路，只不过是更新的数组的值，但是时间复杂度：O(n^2)

还是超时。（ps：为什么都是从后往前，代码三比代码二通过的测试用例要少呢？）

代码四：LogTrick

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = +inf
        for i,j in enumerate(nums):
            if j >= k:
                return 1
            for m in range(i-1,-1,-1):
                if nums[m] | j == nums[m]: #每次OR运算数字都会变大，倘如没有变大就退出
                    break
                nums[m] |= j
                if nums[m] >= k:
                    ans = min(ans,i-m+1)
                    break
        return ans if ans != +inf else -1

思路：

相比代码三多增加了一步if判断，需要着重理解注释的这块。比较难理解，建议观看B站视频解析。

时间复杂度：O(nlogU)
其中 n 是 nums 的长度， U=max(nums) 。由于题目范围二进制数对应集合的大小不会超过 29，因此在 OR 运算下，每个数字至多可以增大 29 次。总体上看，二重循环的总循环次数等于每个数字可以增大的次数之和，即 O(nlogU)。
空间复杂度：O(1) 。

代码五：滑动窗口+栈（理解感觉吃力，使用更难，瞻仰灵神）

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf
        left = bottom = right_or = 0
        for right, x in enumerate(nums):
            right_or |= x
            while left <= right and nums[left] | right_or >= k:
                ans = min(ans, right - left + 1)
                left += 1
                if bottom < left:
                    # 重新构建一个栈
                    for i in range(right - 1, left - 1, -1):
                        nums[i] |= nums[i + 1]
                    bottom = right
                    right_or = 0
        return ans if ans < inf else -1