题目描述
思路解析动画文字版
记牢这一句:最大或 = 后缀的或;要凑齐它,子数组得伸到每个需要的位最近一次出现的地方,取最远的那一个。下面从最右边的下标 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题