【Leetcode 每日一题 - 扩展】3097. 或值至少为 K 的最短子数组 II

问题背景

给你一个 非负 整数数组 $nums$ 和一个整数 $k$。
如果一个数组中所有元素的按位或运算 $OR$ 的值 至少 为 $k$，那么我们称这个数组是 特别的 。
请你返回 $nums$ 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 $-1$。

数据约束

• $1\le nums.length\le 2\times 10^5$
• $0\le nums[i]\le 10^9$
• $0\le k\le 10^9$

解题过程

和 模板题 很像，只是改成了求长度，同样可以用 LogTrick 或是滑窗来解决。

具体实现

LogTrick

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            // 由于单个数字是结果最小的情形，可以直接返回避免后续的冗余计算
            if(cur >= k) {
                return 1;
            }
            // 和暴力解的区别就在于多进行了一个判断，去掉了不必要的遍历
            for(int j = i - 1; j >= 0 && (nums[j] | cur) != nums[j]; j--) {
                nums[j] |= cur;
                if(nums[j] >= k) {
                    res = Math.min(res, i - j + 1);
                }
            }
        }
        // 注意要根据 res 是否被更新过来判断返回的结果
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

滑动窗口

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        int bottom = 0;
        int rightOr = 0;
        for(int left = 0, right = 0; right < nums.length; right++) {
            // 元素从窗口右侧进入
            rightOr |= nums[right];
            while(left <= right && (nums[left] | rightOr) >= k) {
                // 更新结果，注意 left 指针要自增，如果觉得不直观分开写也是可以的
                res = Math.min(res, right - left++ + 1);
                // bottom 始终指向栈底，它在窗口之外表示 rightOr 的结果没有被 nums 数组记录
                if(bottom < left) {
                    // 遍历并把结果更新到 nums 数组中
                    for(int i = right - 1; i >= left; i--) {
                        nums[i] |= nums[i + 1];
                    }
                    // 更新栈底指针
                    bottom = right;
                    // 重置右侧或运算结果
                    rightOr = 0;
                }
            }
        }
        // 注意要根据 res 是否被更新过来判断返回的结果
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}