Smallest Subarrays With Maximum Bitwise OR

You are given a 0-indexed array nums of length $n$, consisting of non-negative integers. For each index $i$ from $0$ to $n - 1$, you must determine the size of the minimum sized non-empty subarray of nums starting at $i$ (inclusive) that has the maximum possible bitwise OR.

In other words, let $B_{ij}$ be the bitwise OR of the subarray nums[i...j] . You need to find the smallest subarray starting at $i$, such that bitwise OR of this subarray is equal to $max(B_{ik})$ where $i \leq k \leq n - 1$.

The bitwise OR of an array is the bitwise OR of all the numbers in it.

Return an integer array answer of size $n$ where answer[i] is the length of the minimum sized subarray starting at $i$ with maximum bitwise OR.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,0,2,1,3]
Output: [3,3,2,2,1]
Explanation:
The maximum possible bitwise OR starting at any index is 3. 
- Starting at index 0, the shortest subarray that yields it is [1,0,2].
- Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1].
- Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1].
- Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3].
- Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3].
Therefore, we return [3,3,2,2,1]. 

Example 2:

Input: nums = [1,2]
Output: [2,1]
Explanation:
Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2.
Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1.
Therefore, we return [2,1].

解题思路

　　比赛的时候做了很久才写出来，思路用的是双指针。或运算是单调的，所以可以开个大小为$32$的哈希表，从前往后扫描，统计出所有数$32$个位上$1$的个数，如果哈希表的第$i$个位置上不为$0$，表示最少存在一个数的第$i$位是$1$，因此可以把大小为$32$的哈希表看作是所有数按位或后的结果。然后用双指针，对于第$i$个位置上的数，往右满足条件的最左边的位置为$j$，证明如果$i$往右移动到${i'}$，那么$j$指针也一定只会往右移动。反证法，假设${i'}$对应的指针为${j'}$，且${j' < j}$，即指针$j$往左移动，那么应该有$s_{{i'}{j'}} = s_{{i'}j}$，$s_{ij}$表示将$i \sim j$这个区间的数按位求或。又因为$s_{ij} = s_{i{i'}} \mid s_{{i'}j} = s_{i{i'}} \mid s_{{i'}{j'}}$，即指针$i$往右最靠左的位置变成了${j'}$，这就产生了矛盾了。

　　如果用哈希表和滑动窗口来实现的话不太好写，这里给出用线段树求区间按位或的做法。思路和上面的一样，用双指针，不过用线段树来得到某个区间按位或的结果。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     struct Node {
 4         int l, r, s;
 5     }tr[100010 * 4];
 6     vector<int> a;
 7     
 8     void build(int u, int l, int r) {
 9         if (l == r) {
10             tr[u] = {l, r, a[l]};
11         }
12         else {
13             int mid = l + r >> 1;
14             build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
15             tr[u] = {l, r, tr[u << 1].s | tr[u << 1 | 1].s};
16         }
17     }
18     
19     int query(int u, int l, int r) {
20         if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
21         int mid = tr[u].l + tr[u].r >> 1, s = 0;
22         if (l <= mid) s = query(u << 1, l, r);
23         if (r >= mid + 1) s |= query(u << 1 | 1, l, r);
24         return s;
25     }
26     
27     vector<int> smallestSubarrays(vector<int>& nums) {
28         int n = nums.size();
29         a = nums;
30         build(1, 0, n - 1);
31         vector<int> ans;
32         for (int i = 0, j = 0; i < n; i++) {
33             if (j < i) j = i;   // j有可能会小于i，比如整个数组的数都相同的时候
34             while (query(1, i, j) < query(1, i, n - 1)) {   // 按位或运算是单调的，因此如果[i~j]的按位或还没有达到最大值时，j就要往右移动
35                 j++;
36             }
37             ans.push_back(j - i + 1);
38         }
39         return ans;
40     }
41 };

　　给出y总的做法，代码就短很多了。

　　当$i$固定后，看一下$j$最小可以取到多少使得按位或为最大值，每一位都是相互独立的，因此可以看一下每一位最小可以在哪个位置，然后所有位的最小位置取个最大值就是答案。对于某个位$k$，如果$i$位置上的这个数的第$k$位为$1$，那么第$k$位的最小位置就是$i$。如果$i$位置上的这个数的第$k$位为$0$，且后面所有数的第$k$位都是$0$，那么第$k$个位置的最小位置就没有，而如果后面存在某个数的第$k$位是$1$，那么第$k$位的最小位置就是往后数的第一个第$k$位是$1$的数的下标。

　　做法是从后往前枚举，如果当前数的某个位为$1$，那么就更新这位的最小位置，如果是$0$则看一下这一位的最小位置是多少，更新最大位置的值。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     vector<int> smallestSubarrays(vector<int>& nums) {
 4         int n = nums.size();
 5         vector<int> cnt(32, -1), ans(n);    // -1表示当前位没有1
 6         for (int i = n - 1; i >= 0; i--) {
 7             int t = i;  // 表示终点最靠左的位置
 8             for (int j = 0; j < 32; j++) {
 9                 if (nums[i] >> j & 1) cnt[j] = i;   // 第j位的最小位置为i
10                 else if (cnt[j] != -1) t = max(t, cnt[j]);  // 如果后面存在某个数的第j位为1，则对最靠左的位置取最大值
11             }
12             ans[i] = t - i + 1;
13         }
14         return ans;
15     }
16 };

参考资料

　　y总，第一名是谁，可以讲一下第一名的代码吗？力扣第87场双周赛：https://www.bilibili.com/video/BV1FV4y1u79H