题目描述
思路解析
一句话答案：LeetCode 2411 按位或最大的最小子数组长度用位运算逆序扫：按位或往右扩只增不减，最大或即后缀或，从右往左记每位最近出现处就能求最短子数组。时间 O(n·32)、空间 O(1)。
每个起点都要一条最短子数组，到底在求什么
给下标从 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⁹，开小会漏高位。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:最大或 = 后缀的或;要凑齐它,子数组得伸到每个需要的位最近一次出现的地方,取最远的那一个。下面从最右边的下标 4 开始,一路往左扫。
先摆好棋盘。数组固定是 [1,0,2,1,3],下标 0 到 4。右边这张 f 表记两件事:第 0 位(值 1)和第 1 位(值 2)各自在当前及右侧最近一次出现在哪个下标,现在还没开始扫,都记「未见」。我们从最右的下标 4 往左走,每到一个数就先拆它的二进制位。
走到下标 4,这里的数是 3,它的二进制是 0b11。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
第 0 位(值 1):3 的二进制 0b11 在这一位是 1,脚下就带着它。把 f[0] 刷新成当前下标 4,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
第 1 位(值 2):3 的二进制 0b11 在这一位是 1,脚下就带着它。把 f[1] 刷新成当前下标 4,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
下标 4 定案。所有需要收集的位算下来,最远要伸到下标 4,所以最短子数组是绿色这一段 [4, 4],长度 1。把 ans[4] 记成 1。answer 现在是 [·, ·, ·, ·, 1],接着往左看下一个。
走到下标 3,这里的数是 1,它的二进制是 0b01。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
第 0 位(值 1):1 的二进制 0b01 在这一位是 1,脚下就带着它。把 f[0] 刷新成当前下标 3,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
第 1 位(值 2):1 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 4。要把它收进按位或,子数组必须从 3 一路伸到 4,长度是 4 减 3 加 1,等于 2。这比当前 t 更远,t 更新成 2。
下标 3 定案。所有需要收集的位算下来,最远要伸到下标 4,所以最短子数组是绿色这一段 [3, 4],长度 2。把 ans[3] 记成 2。answer 现在是 [·, ·, ·, 2, 1],接着往左看下一个。
走到下标 2,这里的数是 2,它的二进制是 0b10。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
第 0 位(值 1):2 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 3。要把它收进按位或,子数组必须从 2 一路伸到 3,长度是 3 减 2 加 1,等于 2。这比当前 t 更远,t 更新成 2。
第 1 位(值 2):2 的二进制 0b10 在这一位是 1,脚下就带着它。把 f[1] 刷新成当前下标 2,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
下标 2 定案。所有需要收集的位算下来,最远要伸到下标 3,所以最短子数组是绿色这一段 [2, 3],长度 2。把 ans[2] 记成 2。answer 现在是 [·, ·, 2, 2, 1],接着往左看下一个。
走到下标 1,这里的数是 0,它的二进制是 0b00。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
第 0 位(值 1):0 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 3。要把它收进按位或,子数组必须从 1 一路伸到 3,长度是 3 减 1 加 1,等于 3。这比当前 t 更远,t 更新成 3。
第 1 位(值 2):0 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 2。要把它收进按位或,子数组必须从 1 一路伸到 2,长度是 2 减 1 加 1,等于 2。这没超过已有的 t = 3,t 保持不变。
下标 1 定案。所有需要收集的位算下来,最远要伸到下标 3,所以最短子数组是绿色这一段 [1, 3],长度 3。把 ans[1] 记成 3。answer 现在是 [·, 3, 2, 2, 1],接着往左看下一个。
走到下标 0,这里的数是 1,它的二进制是 0b01。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
第 0 位(值 1):1 的二进制 0b01 在这一位是 1,脚下就带着它。把 f[0] 刷新成当前下标 0,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
第 1 位(值 2):1 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 2。要把它收进按位或,子数组必须从 0 一路伸到 2,长度是 2 减 0 加 1,等于 3。这比当前 t 更远,t 更新成 3。
下标 0 定案。所有需要收集的位算下来,最远要伸到下标 2,所以最短子数组是绿色这一段 [0, 2],长度 3。把 ans[0] 记成 3。answer 现在是 [3, 3, 2, 2, 1],接着往左看下一个。
从右往左整段扫完,本例最终的 answer 就是 [3, 3, 2, 2, 1]。核心始终只有一条:凑齐后缀的最大按位或,子数组得伸到每个需要的位最近出现的地方,取各位最近出现位置里的最远者。
边界想清:单元素记 1、需要补位就伸到最近出现处、全 0 也每个记 1。
面试重点:最大或即后缀或、从右往左维护每位最近出现的 f 表、时间 O(n 乘 32) 空间常数。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n·32)，n 个下标各扫一遍,每个下标固定看 32 个二进制位,都是常数操作。位数是常数,可视作 O(n) 线性
- 空间：O(32)，按峰值算。只额外用一个长度 32 的 f 表记每位最近出现的下标,与 n 无关,是常数空间;答案数组是输出不计入额外空间
易错点
面试追问把动画讲成自己的话
追问这题的核心观察是什么?
追问为什么要从右往左扫,f 表怎么维护?
追问复杂度是多少,还能更省吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
礼盒的最大甜蜜度
LeetCode 2517 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题