LeetCode 2411中等二分查找
按位或最大的最小子数组长度 图解题解
这道题到底在问什么
给定下标从 0 开始的非负整数数组 nums,长度为 n。对每个 i(0 ≤ i ≤ n-1),在所有以 i 为起点的子数组里,按位或的最大值记作 M;返回能取到 M 且长度最短的那条子数组的长度,组成答案数组 answer。
- 输入
- nums=[1,0,2,1,3]
- 输出
- [3,3,2,2,1]
- 输入
- nums=[1,2]
- 输出
- [2,1]
最优解：一步一步想明白
- 3记牢这一句:最大或 = 后缀的或;要凑齐它,子数组得伸到每个需要的位最近一次出现的地方,取最远的那一个。下面从最右边的下标 4 开始,一路往左扫。
- 4先摆好棋盘。数组固定是 [1,0,2,1,3],下标 0 到 4。右边这张 f 表记两件事:第 0 位(值 1)和第 1 位(值 2)各自在当前及右侧最近一次出现在哪个下标,现在还没开始扫,都记「未见」。我们从最右的下标 4 往左走,每到一个数就先拆它的二进制位。
- 5走到下标 4,这里的数是 3,它的二进制是 0b11。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
- 6第 0 位(值 1):3 的二进制 0b11 在这一位是 1,脚下就带着它。把 f[0] 刷新成当前下标 4,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
- 7第 1 位(值 2):3 的二进制 0b11 在这一位是 1,脚下就带着它。把 f[1] 刷新成当前下标 4,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
- 8下标 4 定案。所有需要收集的位算下来,最远要伸到下标 4,所以最短子数组是绿色这一段 [4, 4],长度 1。把 ans[4] 记成 1。answer 现在是 [·, ·, ·, ·, 1],接着往左看下一个。
- 9走到下标 3,这里的数是 1,它的二进制是 0b01。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
- 10第 0 位(值 1):1 的二进制 0b01 在这一位是 1,脚下就带着它。把 f[0] 刷新成当前下标 3,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
- 11第 1 位(值 2):1 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 4。要把它收进按位或,子数组必须从 3 一路伸到 4,长度是 4 减 3 加 1,等于 2。这比当前 t 更远,t 更新成 2。
- 12下标 3 定案。所有需要收集的位算下来,最远要伸到下标 4,所以最短子数组是绿色这一段 [3, 4],长度 2。把 ans[3] 记成 2。answer 现在是 [·, ·, ·, 2, 1],接着往左看下一个。
- 13走到下标 2,这里的数是 2,它的二进制是 0b10。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
- 14第 0 位(值 1):2 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 3。要把它收进按位或,子数组必须从 2 一路伸到 3,长度是 3 减 2 加 1,等于 2。这比当前 t 更远,t 更新成 2。
- 15第 1 位(值 2):2 的二进制 0b10 在这一位是 1,脚下就带着它。把 f[1] 刷新成当前下标 2,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
- 16下标 2 定案。所有需要收集的位算下来,最远要伸到下标 3,所以最短子数组是绿色这一段 [2, 3],长度 2。把 ans[2] 记成 2。answer 现在是 [·, ·, 2, 2, 1],接着往左看下一个。
- 17走到下标 1,这里的数是 0,它的二进制是 0b00。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
- 18第 0 位(值 1):0 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 3。要把它收进按位或,子数组必须从 1 一路伸到 3,长度是 3 减 1 加 1,等于 3。这比当前 t 更远,t 更新成 3。
- 19第 1 位(值 2):0 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 2。要把它收进按位或,子数组必须从 1 一路伸到 2,长度是 2 减 1 加 1,等于 2。这没超过已有的 t = 3,t 保持不变。
- 20下标 1 定案。所有需要收集的位算下来,最远要伸到下标 3,所以最短子数组是绿色这一段 [1, 3],长度 3。把 ans[1] 记成 3。answer 现在是 [·, 3, 2, 2, 1],接着往左看下一个。
- 21走到下标 0,这里的数是 1,它的二进制是 0b01。答案的下限永远是 1,因为哪怕别的都不管,子数组至少可以只取它自己一格,所以 t 先记成 1。接着逐位看:每一位要么它自己就有,要么得靠右边补。
- 22第 0 位(值 1):1 的二进制 0b01 在这一位是 1,脚下就带着它。把 f[0] 刷新成当前下标 0,表示这一位最近就出现在这里。要收集它,子数组只要覆盖自己这一格,长度 1,不会撑大 t。
- 23第 1 位(值 2):1 在这一位是 0,自己没有。但后缀里这一位出现过,最近落在右边下标 2。要把它收进按位或,子数组必须从 0 一路伸到 2,长度是 2 减 0 加 1,等于 3。这比当前 t 更远,t 更新成 3。
- 24下标 0 定案。所有需要收集的位算下来,最远要伸到下标 2,所以最短子数组是绿色这一段 [0, 2],长度 3。把 ans[0] 记成 3。answer 现在是 [3, 3, 2, 2, 1],接着往左看下一个。
- 25从右往左整段扫完,本例最终的 answer 就是 [3, 3, 2, 2, 1]。核心始终只有一条:凑齐后缀的最大按位或,子数组得伸到每个需要的位最近出现的地方,取各位最近出现位置里的最远者。
⚠️ 容易写错的地方
✗ 错：真的去枚举每个起点的所有子数组求最大或
✓ 对：看清最大或就是后缀的或,一遍从右往左扫即可
按位或往右扩只增不减,枚举是 O(n²) 甚至更糟,而利用单调性一遍就够
✗ 错：f[j] 记成该位最靠右的出现位置
✓ 对：f[j] 要记最近一次(离 i 最近的右侧)出现
从右往左扫时每遇到该位就覆盖 f[j],它自然保存的是离当前 i 最近的右侧下标,凑齐这一位只要伸到最近处
✗ 错：答案下限写 0 或忘了设下限
✓ 对：t 至少是 1
子数组非空,起点自己那一格总能取,最短长度不会小于 1
✗ 错：位数只开到能覆盖单个数,忽略大值
✓ 对：开满 32 位
nums[i] 可达 10 的 9 次方,接近 2 的 30 次方,位数开小会漏掉高位
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(n·32)
n 个下标各扫一遍,每个下标固定看 32 个二进制位,都是常数操作。位数是常数,可视作 O(n) 线性
空间
O(32)
按峰值算。只额外用一个长度 32 的 f 表记每位最近出现的下标,与 n 无关,是常数空间;答案数组是输出不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 按位或最大的最小子数组长度 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心观察是什么?+
从某个起点出发的最大按位或,就是从它到数组末尾整段后缀的按位或,因为按位或往右扩只增不减。要用最短子数组凑齐这个最大或,只需伸到后缀里每个出现过的二进制位最近一次出现的位置,取最远的那个。
为什么要从右往左扫,f 表怎么维护?+
从右往左扫,f[j] 自然保存当前及右侧该位最近一次出现的下标:每遇到 nums[i] 的第 j 位是 1 就把 f[j] 覆盖成 i。对每个 i,遍历 32 位,自己有的位更新 f、自己没有但右边有的位用 f[j]-i+1 更新答案上界。
复杂度是多少,还能更省吗?+
时间 O(n 乘 32),每个下标固定看 32 位,视位数为常数就是线性 O(n);空间只用一张长度 32 的 f 表,是 O(1) 常数。位数是数据类型决定的常数,已经是这一类做法里很紧的复杂度。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 按位或最大的最小子数组长度 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。