本题要找最小窗口长度 k,使每个长度为 k 的子数组的按位或都等于整个数组的或值 T。
先求出 T。若 T=0,说明全是 0,任意窗口或都是 0,答案为 1。
T 里出现过的每一位 b,都必须出现在每一个长度为 k 的窗口里。这等价于:把该位取 1 的下标列出,再在两端加上哨兵 -1 与 n,相邻下标的最大间距就是这位所要求的最小 k。对所有位取最大值即为答案。
直观上,某位两次出现之间隔得越远,窗口就要越长才能「兜住」这一位。
周末练球房里,陪练按顺序喂了 n 个多球,第 i 个球的力度记在数组 hits 里(非负整数)。教练回放时用按位或看一段球的「综合力度」:一段连续击球 [l,r](下标从 0 计)的综合力度是 hits[l]∨hits[l+1]∨⋯∨hits[r]。
教练希望找到最小的整数 k,使得任意长度为 k 的连续窗口,综合力度都等于整串的综合力度(即所有元素的按位或)。这样剪一段长度为 k 的录像,无论从哪一拍开始,都不会丢掉任何一位力度特征。
k 必须满足 1≤k≤n。可以证明这样的 k 一定存在(取 k=n 即可)。
请实现:
minForceWindow(hits: int[]) -> int
一行:整型数组 hits,形如 [1, 2, 3]。
约束:
一个整数:最小合法 k。
输入:
[1, 2, 3]
输出:
2
说明:整串按位或为 3。长度为 1 的窗口分别是 1、2、3,其中 1、2 都不够;长度为 2 的窗口 [1,2] 与 [2,3] 的或都是 3。
输入:
[8, 1, 2]
输出:
3
说明:整串或为 11。高位 8 只在开头出现一次,长度为 2 的窗口 [1,2] 或为 3,缺了这一位,因此必须取整段 k=3。
输入:
[0, 0, 0]
输出:
1
说明:全程力度为 0,任意窗口的或都是 0,最短 k=1。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册