题目分析

本题的难度也不大，因为本题有一些技巧可以使用，因此决定分享给小伙伴们。

双指针

本题要找按位或的最大值所对应的最短子数组长度，有一种笨方法是使用后缀和，用一个数组记录curSum[n]，表示以第n个元素开始，最大值中1出现的总次数。

然后利用双指针去求解，这里注意指针右移和左移的时候要记录每一位的1的个数，因为某些位可能有多个1。当有1的位数等于curSum[n]时，表示已经到了最大值，此时可以将left指针右移了。

算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] curSum = new int[n];
        int currentVal = nums[n - 1];
        curSum[n - 1] = getBit(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            currentVal |=  nums[i];
            curSum[i] = getBit(currentVal);

        }
        int[] res = new int[n];
        int[] cur = new int[30];
        Arrays.fill(res, 1);
        int left = 0, right = 0;
        for (; right < n && left < n; left++) {
            while (right < n && isOk(curSum[left], cur)) {
                update(cur, nums[right++], 1);
            }
            res[left] = Math.max(right - left, 1);
            update(cur, nums[left], -1);
        }
        for (int i = left; i < n; i++) {
            res[i] = Math.max(right - i, 1);
        }
        return res;
    }

    private boolean isOk(int val, int[] bit) {
        int res = 0;
        for (int i = 0; i < 30; i++) {
            if (bit[i] != 0) {
                res++;
            }
        }
        return res < val;
    }

    private void update(int[] cur, int val, int flag) {
        for (int i = 0; i < 30; i++) {
            if ((val & (1 << i)) != 0) {
                cur[i] += flag;
            }
        }
    }

    private int getBit(int x) {
        int res = 0;
        while (x != 0) {
            x -= x & -x;
            res += 1;
        }
        return res;
    }
}

位运算

本题的最优解是位运算，但是本题的位运算有特殊的含义，是真的按位进行运算。

我们思考是不是可以对每一位求出现1的最短长度，记作bit[30]，然后对前30位求最大值，前30位中，哪一位出现1最晚，那最大长度就是它。

我们可以从后向前遍历，查找最近一次出现1的位置。假设当前遍历到i，如果第j位是1，则更新该位bit[j] = i。否则要计算最大值res[i] = max(res[i], bit[j] - i + 1)，这样不需要重新统计一次最大值。因为要连上本身，所以要+1。

这里要注意要给一开始赋值为1，因为最少需要一位(自身)，如果某个元素本身就是最大值，那么按照上述算法结果是0。

如果第j为是1，则不需要计算最大值，小伙伴也都能理解，如果某一位是j，那说明该位出现1的最短长度是1，就是本身，计算也是i - i + 1，等于1，而res[i]的最小值就是1，所以max(res[i], 1) = res[i]，就不用计算了。

算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] bit = new int[30];
        for (int i = n - 1; i >= 0; i--) {
            res[i] = 1;
            for (int j = 0; j < 30; j++) {
                if ((nums[i] & (1 << j)) != 0) {
                    bit[j] = i;
                } else {
                    res[i] = Math.max(res[i], bit[j] - i + 1);
                }
            }
        }
        return res;
    }
}

刷题总结

位运算的精髓不仅仅是一些小技巧，如寻找最低为的x & -x，而是真正利用位运算，将某些32为的数拆解为32个bit优化计算。