Leetcode 2411. Smallest Subarrays With Maximum Bitwise OR

[Woodyiiiiiii]

这道题我一直在尝试找到某种规律，但最后还没找到。

关键是从位数思考|与最大值的关系。

对于某个数nums[i]，要往后循环找到最大的数，就是尽可能在位数上获得更多的、最近的1。所以提前预处理，向前遍历存储在每个节点上最近1位数的位置。

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        // the last appearance of index bits
        int[] last = new int[32];
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = 1;
            for (int j = 0; j < 32; ++j) {
                if ((nums[i] & (1 << j)) > 0) {
                    last[j] = i;
                }
                ans[i] = Math.max(ans[i], last[j] - i + 1);
            }
        }
        return ans;
    }
}

---

• 2411. Smallest Subarrays With Maximum Bitwise OR
• https://leetcode.com/problems/smallest-subarrays-with-maximum-bitwise-or/solutions/2588015/java-c-python-bit-solution-with-explanation/