按位或最大的最小子数组长度 图解题解

每个起点都要一条最短子数组，到底在求什么

给下标从 0 开始的非负整数数组 nums，长 n。对每个起点 i，看从 i 出发往右的所有子数组，按位或（两个数逐个二进制位比，有 1 就是 1）的最大值记作 M；再挑能达到 M 的最短子数组，长度填进答案。题面 nums=[1,0,2,1,3] 答案 [3,3,2,2,1]：下标 4 的 3 就是全局最大或，长度 1；下标 0 凑够它得伸到 [1,0,2]，长度 3。

把每个起点的所有子数组都或一遍，要多久

对每个起点把从它出发的每条子数组都或一遍、记下最大或和最短长度，这是最先冒出来的走法。可枚举「起点 × 终点」就有约 n²/2 对，每对再挨个或起来，总账滑到 O(n³)；哪怕边扩边攒当前或省掉最内层，仍是 O(n²)。n 上万这两条都跑不动。

按位或往右扩只增不减，这条性质能省掉多少活

盯住按位或一个死性质：往子数组里越加元素，某个二进制位一旦成 1 就不会变回 0，结果只增不减。所以从 i 出发的最大或，就是从 i 一直或到数组末尾那整条后缀（从某下标到末尾的一段）的或。问题变成：凑齐后缀或，子数组最短伸到哪？后缀或里每有一个是 1 的位，子数组就得包含一个在这位上为 1 的数，才算盖住它一次。盖住某位只要伸到它在 i 右侧最近一次出现的下标；各位里最远的下标就把右端定下来。

从右往左扫，一张长度 32 的表怎么记住每一位

顺着这个观察从右往左扫，一张表就能维护每位的最近出现处：开长度 32 的数组 f，f[j] 记第 j 位在当前及右侧最近一次出现的下标，起手全填 -1。扫到下标 i，先把答案下限 t 记成 1；再逐位看 0 到 31：nums[i] 这一位是 1 就把 f[j] 刷成 i；是 0 而 f[j] 不是 -1（右边出现过），就伸到 f[j]，长度 f[j]-i+1，更新 t 取最大。i 处理完，t 就是 ans[i]。

[1,0,2,1,3] 从下标 4 往左，每格答案怎么定

只涉及第 0 位（值 1）和第 1 位（值 2）。下标 4 是 3=0b11：两位都自带，f[0]、f[1] 记 4，ans[4]=1。下标 3 是 1=0b01：第 0 位刷 f[0]=3；第 1 位靠 f[1]=4，得 4-3+1=2，ans[3]=2。下标 2 是 2=0b10：第 0 位靠 f[0]=3 得 2；第 1 位刷 f[1]=2；ans[2]=2。下标 1 是 0=0b00：第 0 位靠 f[0]=3 得 3；第 1 位得 2 没超；ans[1]=3。下标 0 是 1=0b01：第 0 位刷 f[0]=0；第 1 位靠 f[1]=2 得 3；ans[0]=3。得 [3,3,2,2,1]。

下限忘了钉成 1，遇上全 0 那段就交白卷

n 个下标各扫固定 32 位，时间 O(n·32)，位数当常数即线性 O(n)；只额外用长度 32 的 f 表，空间 O(1)。坑各有后果：t 下限得是 1，起点自己那格总能取，写成 0 会让全 0 的段返回错值；f[j] 该记最近一次出现、而非整个数组最靠右的位置，从右往左扫每遇到就覆盖；位数得开满 32，nums[i] 可达 10⁹，开小会漏高位。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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;
    }
};

Java

import java.util.*;
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;
    }
}