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

一、题目描述

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。

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

换言之，令 Bij 表示子数组 nums[i…j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。

一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

示例：

输入：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] 。

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 109

二、解题思路

整数就 32 位，题目都是非负整数，所以或运算后最多也就是低 31 位全都是 1。

• 或运算结果越大，实际就是 31 位中 1 的数量越多

要是知道 31 位整数中每一位 1 出现的位置 indexes，那就能知道或运算达到最大值的地方。

或运算结果最大的最短子数组，就是：

• 从当前索引 i，到 32 位 1 索引最大值的区间 [i, max(indexes)]

题目限制了范围大于 0 小于 10^9，所以只需要低 30 位就够了。

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

private int[] smallestSubarrays(int[] nums) {
    // 整数低 30 位出现 1 的最小索引
    int[] indexes = new int[30];
    Arrays.fill(indexes, -1);

    int n = nums.length;
    int[] ans = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int maxIndex = i;
        for (int j = 0; j < 30; j++) {
            int exist = (nums[i] >>> j) & 1;
            if (exist > 0) {
                // 当前数字有第 j 位的 1
                // 因为是求最短子数组，所以更新索引为更小值
                indexes[j] = i;
            } else if (indexes[j] != -1) {
                // 找出 30 位 1 索引的最大值
                maxIndex = Math.max(maxIndex, indexes[j]);
            }
        }
        ans[i] = maxIndex - i + 1;
    }
    return ans;
}