# [2411. 按位或最大的最小子数组长度](https://leetcode.cn/problems/smallest-subarrays-with-maximum-bitwise-or)
[English Version](/solution/2400-2499/2411.Smallest%20Subarrays%20With%20Maximum%20Bitwise%20OR/README_EN.md)
## 题目描述
<!-- 这里写题目描述 -->
<p>给你一个长度为 <code>n</code> 下标从 <strong>0</strong> 开始的数组 <code>nums</code> ，数组中所有数字均为非负整数。对于 <code>0</code> 到 <code>n - 1</code> 之间的每一个下标 <code>i</code> ，你需要找出 <code>nums</code> 中一个 <strong>最小</strong> 非空子数组，它的起始位置为 <code>i</code> （包含这个位置），同时有 <strong>最大</strong> 的 <strong>按位或</strong><b>运算值</b> 。</p>
<ul>
<li>换言之，令 <code>B<sub>ij</sub></code> 表示子数组 <code>nums[i...j]</code> 的按位或运算的结果，你需要找到一个起始位置为 <code>i</code> 的最小子数组，这个子数组的按位或运算的结果等于 <code>max(B<sub>ik</sub>)</code> ，其中 <code>i <= k <= n - 1</code> 。</li>
</ul>
<p>一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。</p>
<p>请你返回一个大小为 <code>n</code> 的整数数组<em> </em><code>answer</code>，其中<em> </em><code>answer[i]</code>是开始位置为 <code>i</code> ，按位或运算结果最大，且 <strong>最短</strong> 子数组的长度。</p>
<p><strong>子数组</strong> 是数组里一段连续非空元素组成的序列。</p>
<p> </p>
<p><strong>示例 1：</strong></p>
<pre><b>输入：</b>nums = [1,0,2,1,3]
<b>输出：</b>[3,3,2,2,1]
<strong>解释：</strong>
任何位置开始，最大按位或运算的结果都是 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] 。
</pre>
<p><strong>示例 2：</strong></p>
<pre><b>输入：</b>nums = [1,2]
<b>输出：</b>[2,1]
<strong>解释：
</strong>下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
所以我们返回 [2,1] 。
</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li><code>n == nums.length</code></li>
<li><code>1 <= n <= 10<sup>5</sup></code></li>
<li><code>0 <= nums[i] <= 10<sup>9</sup></code></li>
</ul>
## 解法
<!-- 这里可写通用的实现逻辑 -->
**方法一：逆序遍历**
要找到每个以 $i$ 作为起始位置的最短子数组，满足或运算结果最大，那么必须让这个结果的 $1$ 尽可能多。
我们用一个 $32$ 位大小的数组$f$ 来记录每一位 $1$ 最早出现的位置。
逆序遍历数组 `nums[i]`，对于 `nums[i]` 数字中的第 $j$ 位，如果为 $1$，那么 $f[j]$ 就是 $i$。否则如果 $f[j]$ 不为 $-1$，说明右侧找到了满足第 $j$ 位为 $1$ 的数字，更新长度。
时间复杂度 $O(n\log m)$。其中 $n$ 为数组 `nums` 的长度，而 $m$ 为数组 `nums` 中的最大值。
<!-- tabs:start -->
### **Python3**
<!-- 这里可写当前语言的特殊实现逻辑 -->
```python
class Solution:
def smallestSubarrays(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
f = [-1] * 32
for i in range(n - 1, -1, -1):
t = 1
for j in range(32):
if (nums[i] >> j) & 1:
f[j] = i
elif f[j] != -1:
t = max(t, f[j] - i + 1)
ans[i] = t
return ans
```
### **Java**
<!-- 这里可写当前语言的特殊实现逻辑 -->
```java
class Solution {
public int[] smallestSubarrays(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
int[] f = new int[32];
Arrays.fill(f, -1);
for (int i = n - 1; i >= 0; --i) {
int t = 1;
for (int j = 0; j < 32; ++j) {
if (((nums[i] >> j) & 1) == 1) {
f[j] = i;
} else if (f[j] != -1) {
t = Math.max(t, f[j] - i + 1);
}
}
ans[i] = t;
}
return ans;
}
}
```
### **C++**
```cpp
class Solution {
public:
vector<int> smallestSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> f(32, -1);
vector<int> ans(n);
for (int i = n - 1; ~i; --i) {
int t = 1;
for (int j = 0; j < 32; ++j) {
if ((nums[i] >> j) & 1) {
f[j] = i;
} else if (f[j] != -1) {
t = max(t, f[j] - i + 1);
}
}
ans[i] = t;
}
return ans;
}
};
```
### **Go**
```go
func smallestSubarrays(nums []int) []int {
n := len(nums)
f := make([]int, 32)
for i := range f {
f[i] = -1
}
ans := make([]int, n)
for i := n - 1; i >= 0; i-- {
t := 1
for j := 0; j < 32; j++ {
if ((nums[i] >> j) & 1) == 1 {
f[j] = i
} else if f[j] != -1 {
t = max(t, f[j]-i+1)
}
}
ans[i] = t
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
```
### **TypeScript**
```ts
```
### **...**
```
```
<!-- tabs:end -->