LeetCode 第3097题：按位或值至少为 K 的最短子数组 II

LeetCode 第3097题：按位或值至少为 K 的最短子数组 II

在本文中，我们将深入探讨 LeetCode 第3097题：按位或值至少为 K 的最短子数组 II。我们将详细解析题目描述，理解约束条件，并逐步讲解一个高效的 Python 解法，帮助你有效解决这一问题。

题目描述

给定一个 非负整数数组 nums 和一个整数 k，请你找到 nums 中满足以下条件的 最短非空子数组 的长度：

• 子数组中所有元素的 按位或运算（OR） 的值 至少为 k。

如果不存在这样的子数组，则返回 -1。

定义

• 按位或（OR）：一种二进制运算，对应位上有一个为 1 时结果位为 1，否则为 0。例如：

  1 | 2 = 3
  2 | 1 = 3
  

• 子数组：数组中连续的一部分元素。

示例

示例 1：

输入：nums = [1, 2, 3], k = 2
输出：1
解释：
子数组 [3] 的按位或值为 3，满足 3 >= 2，所以返回 1。

示例 2：

输入：nums = [2, 1, 8], k = 10
输出：3
解释：
子数组 [2, 1, 8] 的按位或值为 11，满足 11 >= 10，所以返回 3。

示例 3：

输入：nums = [1, 2], k = 0
输出：1
解释：
任何非空子数组的按位或值都至少为 0，所以返回 1。

约束条件

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 10^9
• 0 <= k <= 10^9

解题思路

要高效地解决这个问题，我们可以采用 贪心算法 结合 按位运算 的特性，来优化寻找满足条件的最短子数组的过程。

关键观察点

1. 即时满足：如果数组中存在一个元素本身就大于或等于 k，那么最短的子数组长度为 1。

2. 按位或的单调性：随着子数组长度的增加，按位或的结果值要么保持不变，要么增加。这一特性可以帮助我们优化搜索过程。

3. 状态追踪：通过维护一个字典，记录每个可能的按位或结果及其对应的最短子数组长度，可以有效减少重复计算。

具体步骤

1. 初始化：设置一个变量 ans 为无穷大，用于记录当前找到的最短子数组长度。

2. 遍历数组：

   • 对于数组中的每一个元素 x，如果 x 本身就大于或等于 k，立即返回 1。
   • 否则，尝试将当前元素与之前的元素进行按位或操作，更新之前元素的按位或值。
   • 如果某个更新后的按位或值满足条件，则更新 ans 为当前子数组长度。

3. 结果判断：遍历完成后，如果 ans 仍为无穷大，说明不存在满足条件的子数组，返回 -1。否则，返回 ans。

代码实现

以下是上述思路的 Python 实现：

from typing import List

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = float('inf')  # 初始化答案为无穷大
        for i, x in enumerate(nums):
            if x >= k:
                return 1  # 如果当前元素满足条件，返回1
            j = i - 1
            while j >= 0 and (nums[j] | x) != nums[j]:
                nums[j] |= x  # 更新前一个元素的按位或值
                if nums[j] >= k:
                    ans = min(ans, i - j + 1)  # 更新最短子数组长度
                j -= 1
        return ans if ans < float('inf') else -1  # 返回最终结果

代码解析

1. 初始化：

   ans = float('inf')
   

   • 将 ans 初始化为无穷大，表示尚未找到满足条件的子数组。

2. 遍历数组元素：

   for i, x in enumerate(nums):
   

   • 使用 enumerate 遍历数组，同时获取元素的索引 i 和值 x。

3. 单元素检查：

   if x >= k:
       return 1
   

   • 如果当前元素 x 本身就满足 x >= k，则最短子数组长度为 1，直接返回。

4. 更新按位或值：

   j = i - 1
   while j >= 0 and (nums[j] | x) != nums[j]:
       nums[j] |= x
       if nums[j] >= k:
           ans = min(ans, i - j + 1)
       j -= 1
   

   • 初始化 j 为当前元素的前一个元素索引。
   • 使用 while 循环向前遍历，更新前一个元素的按位或值。
   • 如果更新后的值满足 nums[j] >= k，则更新 ans 为当前子数组长度与已有最短长度的较小值。
   • 循环终止条件为索引越界或按位或操作后值不变，避免不必要的计算。

5. 返回结果：

   return ans if ans < float('inf') else -1
   

   • 如果 ans 被更新过，返回其值；否则，返回 -1，表示不存在满足条件的子数组。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 虽然内层循环看似可能达到 O(n^2)，但由于按位或操作的性质，实际上每个元素的按位或值最多变化 30 次（因为 nums[i] 最大为 10^9，二进制表示不超过 30 位），所以整体时间复杂度为线性。

• 空间复杂度：O(1)。

  • 我们在原地修改了输入数组 nums，并且只使用了常数级别的额外空间。

示例解析

以 示例 1 为例：

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

• 迭代 1 (i = 0, x = 1):

  • 1 < 2，继续。
  • j = -1（没有前一个元素），跳过。

• 迭代 2 (i = 1, x = 2):

  • 2 >= 2，满足条件，立即返回 1。

因此，函数正确返回 1。

结论

通过利用按位或操作的单调性和贪心策略，我们能够高效地找到满足条件的最短子数组。这种方法不仅时间复杂度低，而且实现简洁，适用于处理大规模的数据输入。

如果你有任何疑问或更优化的解法，欢迎在评论区交流分享！

原文地址：https://blog.csdn.net/qq_17405059/article/details/145182104

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！