1. 先把题面翻译成人话构造最小位运算数组到底在还原什么1.1 位运算数组不是新概念就是相邻按位或的结果如果你和我一样点开 Leetcode 3314 构造最小位运算数组 I 之前以为它是个简单枚举题那读完题面大概会愣一下“最小”两个字才是全题的重心。位运算题最怕的不是不会用 | ^而是不知道在哪里用贪心、在哪里用暴力。这篇文章就把构造最小位运算数组 I 的完整思路拆开从位独立讲到连续段填充再给出一版可以直接提交的 Python 代码。适合刚刷完数组基础题、准备进阶位运算的读者如果你已经被 994 腐烂的橘子这类 BFS 题虐过换个脑子来做做构造题也挺好。先明确题目里的“位运算数组”到底是什么意思。设原数组为a长度为n。位运算数组b是这样得到的对每个下标i都有b[i] a[i] | a[i 1]也就是说b是相邻两个元素做按位或之后得到的结果数组它的长度是n - 1。题目给你b让你把a还原出来。这本质上是一道“给结果、求原因”的构造题。举个具体例子。如果n 3b [1, 3]那么可行解并不唯一a [0, 1, 3]0 | 1 11 | 3 3成立。a [1, 0, 3]1 | 0 10 | 3 3也成立。a [1, 1, 2]1 | 1 11 | 2 3还是成立。如果只要求“找一组可行解”随便填都能过。但题目偏偏要“最小”于是问题一下子从枚举变成了构造。1.2 “最小”意味着字典序最小不是数值最小数组比大小莱科德这类题目默认按字典序比。所谓字典序就是从头开始比较第一个不同的元素哪个数更小哪个数组就更小。如果第一个元素相同再比第二个依次类推。所以上面三个候选里[0, 1, 3]是最小的因为它的第一个元素是0而另外两个第一个元素都是1。这给我们的启发很直接构造的时候必须优先让a[0]尽量小然后让a[1]尽量小再让a[2]尽量小……也就是一个标准的贪心过程。但贪心不能瞎贪。你让a[0]变成0很可能把压力全部甩给a[1]如果a[1]被逼成了一个大数后面反而可能无解。所以必须先理解位运算的底层性质再决定每一步怎么填。2. 核心原理为什么每一位可以单独决定2.1 位独立把一个大问题拆成 30 个小问题位运算最容易被忽略、但最好用的性质是不同二进制位之间完全独立。a[i] | a[i 1]的第k位只由a[i]和a[i 1]的第k位决定。高位是1还是0完全不影响低位的结果。所以我们可以把b拆成一层一层的二进制位每一层单独构造一个“只含 0/1 的数组”最后再把所有层的构造结果按位或回去。举个例子。如果b [2, 3]二进制分别是10和11。那么第0层最低位的bits是[0, 1]第1层的bits是[1, 1]。两层互不干扰分别把a的对应位填好再合并就是最终答案。这个拆位思想在很多数组相关题目里都适用尤其是当题目里出现“按位与”“按位或”“按位异或”这种字眼时先问自己一句能不能把每个二进制位单独拎出来看多半是能的。2.2 0 是硬约束1 只是“至少有一个 1”在某一层里设bit[i]是b[i]的第k位a[i]和a[i 1]的第k位分别记为x[i]、x[i 1]。那么约束只有两种情况如果bit[i] 0因为按位或的结果是0说明x[i]和x[i 1]必须都是 0。这是硬性条件没有任何商量余地。如果bit[i] 1说明x[i]和x[i 1]至少有一个是1唯一禁止的情况是“两个都是 0”。所以整道题可以简化成一句话有一堆位置因为相邻的bit[i] 0被强制填成 0剩下的位置要尽量填 0但不能出现“相邻两个都是 0”这种非法状态。这比直接处理整个整数简单太多了。因为每一层只有 0 和 1 两种取值所有复杂决策都被压缩成“这里能不能填 0”。2.3 连续 1 段里的填充规则现在只看某一层。假设这一层的bits是bits [1, 1, 0, 1]bits[2] 0会强制x[2] 0、x[3] 0。于是整个数组被这个硬性 0 切成了两段左边一段bits[0]和bits[1]都是 1对应位置x[0]、x[1]、x[2]。右边一段bits[3]是 1对应位置x[3]、x[4]。在每一段内部规则只剩下一个相邻两个x不能同时为 0。这时候贪心就非常简单了第一个位置先尝试填 0因为越靠前越小。如果前一个位置已经是 0那当前位置必须填 1否则会出现“00”。如果前一个位置是 1那当前位置优先填 0。比如bits [1, 1, 1]时a的对应位长度是 4。按照上面的规则填出来是x [0, 1, 0, 1]验证一下0 | 1 11 | 0 10 | 1 1完全成立。而且它比[1, 0, 1, 0]小因为第一个位置是 0。再看一个带硬性 0 的例子。bits [1, 0, 1]bits[1] 0直接让x[1] 0、x[2] 0。左侧bits[0] 1但x[1]已经是 0所以x[0]只能填 1。右侧bits[2] 1但x[2]已经是 0所以x[3]只能填 1。最终结果是x [1, 0, 0, 1]这个例子特别能说明问题不要因为“优先填 0”就无脑给首位置填 0还要看后面有没有被硬性 0 卡住。3. 代码落地按位跑连续段和你想的暴力回溯不一样3.1 整体流程先拆位后填段最后统一验证实际写代码的时候没必要在每一位上都做复杂的可行性判断。我用的流程是固定的四步枚举二进制位k把b拆成这一层的bits。遍历bits把所有bit[i] 0的位置标成“强制填 0”也就是x[i]和x[i 1]都必须为 0。找bits里所有连续的“1 段”对每一段单独做贪心填充。所有位都填完后统一验证一遍(a[i] | a[i 1]) b[i]如果不成立就返回空数组。最后一步非常重要因为按位独立构造时某一层局部可行不代表整体一定可行。比如bits [0, 1, 0]这一层bits[0] 0让x[0]、x[1]都是 0bits[2] 0让x[2]、x[3]都是 0但中间的bits[1] 1又要求x[1] | x[2] 1这显然是矛盾的。所以必须在最后做一次整体校验把所有层叠加起来再看。3.2 Python 实现下面这版代码可以直接提交核心逻辑都在_build_segment里。from typing import List class Solution: def minBitwiseArray(self, b: List[int]) - List[int]: n len(b) 1 ans [0] * n # 按二进制位逐层处理31 位足够覆盖常见的 int 范围 for k in range(31): bits [(v k) 1 for v in b] # fixed[i] True 表示这一层里 a[i] 必须为 0 fixed [False] * n for i, x in enumerate(bits): if x 0: fixed[i] True fixed[i 1] True i 0 while i n - 1: if bits[i] 1: l i while i n - 1 and bits[i] 1: i 1 r i - 1 length r - l 2 start_zero fixed[l] end_zero fixed[r 1] seg self._build_segment(length, start_zero, end_zero) for j in range(length): if seg[j]: ans[l j] | (1 k) else: i 1 # 整体校验不能省 for i in range(n - 1): if (ans[i] | ans[i 1]) ! b[i]: return [] return ans def _build_segment(self, length: int, start_zero: bool, end_zero: bool) - List[int]: seg [0] * length for i in range(length): # 边界位置被硬性 0 卡住 if (i 0 and start_zero) or (i length - 1 and end_zero): seg[i] 0 continue # 前一个位置已经是 0当前位置必须补 1 if i 0 and seg[i - 1] 0: seg[i] 1 continue # 如果右边是强制 0且再往下填 0 会导致最后两个都是 0 if end_zero and i length - 2: seg[i] 1 continue # 其他情况优先填 0 seg[i] 0 return seg整个实现的核心其实只有三条填值规则被硬性 0 卡住的位置只能填 0。前一个是 0当前位置为了不出现“00”只能填 1。当前位置是“强制 0 端点的前一个位置”时如果填 0最后的强制的 0 会和它相邻形成“00”所以必须填 1。3.3 复杂度与为什么这版可以直接交时间复杂度是O(n * 31)因为每一层都要遍历一遍b和ans。空间复杂度是O(n)主要用来存bits、fixed和ans。这个复杂度对 I 版本来说绰绰有余。就算n到10^531 层循环也不过是三百多万次操作Python 完全跑得动。II 版本如果只是把n拉大、把数值范围拉高这版代码的思路依然成立不需要换算法。很多人看到“位运算”三个字就想上 DFS、回溯其实没有必要。这道题真正考的是能不能把位压到单层去理解能不能在连续段里做贪心。暴力枚举当然也能过小数据但那样收获不大。4. 我实际提交时踩过的坑全零数组、无解判定、位宽4.1 坑一无解时返回了半成品我先说一个最容易犯的错构造完所有二进制位之后没有做整体校验直接返回ans。问题是按位独立构造时每一层看起来都“局部正确”但合并起来可能无解。最典型的就是某一层出现了bits [0, 1, 0]这种情况。bits[0] 0强制a[0]、a[1]的这一位都是 0bits[2] 0强制a[2]、a[3]的这一位都是 0中间的bits[1] 1又要求a[1]和a[2]至少有一个 1。这根本不可能成立。如果不做最后校验ans里这一层全是 0表面上也能返回一个数组但放到(ans[i] | ans[i 1]) b[i]里一验就露馅。所以我在代码里专门加了一步全部位填完后再跑一遍原约束一旦发现不相等立刻返回空数组。4.2 坑二把首位贪心理解得太死另一个坑是只记住了“优先填 0”结果在连续 1 段里填错。比如某一层的bits [1, 1, 1]正确的最小结果是[0, 1, 0, 1]。但有人会想第一个位置优先填 0第二个位置也优先填 0结果变成[0, 0, ?]直接违反约束。还有人会把第一个位置填成 1得到[1, 0, 1, 0]虽然可行但不是最小。正确的理解是优先填 0 的前提是后面还能接得住。一旦前一个位置是 0当前位置就必须填 1否则就会出现两个连续的 0。这比“所有位置都尽量填 0”更准确。遇到右端点是强制 0 的情况还要额外往前推一步让倒数第二个位置填 1否则末尾也会出现“00”。4.3 坑三位宽不够最高位被吞掉还有一次我图省事只循环到range(30)结果某个用例里b[i]的最高位是第 30 位直接被我漏掉了。构造出来的ans在最后校验时全部对不上排查半天才发现是位宽问题。建议不要凭感觉写死一个位数可以直接取所有b[i]的最大二进制位长度max_bit max(b).bit_length() if b else 1 for k in range(max_bit): ...这样既不会漏位也不会多做无用的高位循环。如果题目里数值可能到2^31级别那就用 31 位如果按位与/异或题里可能出现负数更要格外小心Python 的负数和 C 的补码表示不太一样刷题时最好先确认数据范围。4.4 坑四数组初始化带来的额外心理负担这道题涉及的数组不多但数组初始化的习惯还是值得说一下。ans [0] * n和fixed [False] * n都是一维数组直接乘号初始化就好。有些朋友刚从二维数组、指针数组那边转过来喜欢顺手写[[0] * n]结果发现多了一层括号后面索引经常错位。其实构造题里的“累加位”操作很常见先初始化成全 0再根据每一层的贪心结果往对应位置用| (1 k)累加。不要试图直接算出一个完整整数那样反而容易在位上出错。5. 从 I 到 II同一套思路如何迁移5.1 I 和 II 的差异本质是数据规模很多时候LeetCode 的题目分成 I 和 II 两个版本I 版本数据范围小可以用更暴力的方法II 版本数据范围大必须上更优的做法。但构造最小位运算数组这题有点特别核心思路本身已经是线性复杂度所以 I 和 II 的差距不大。真正需要注意的是I 版本可能允许你直接对每个位置做一次小范围枚举比如从 0 试到当前b里的最大值再验证相邻或的结果。II 版本如果把n拉到10^5、把数值范围拉到2^31暴力枚举就完全不可行了。这时候按位拆解 连续段贪心的优势就出来了。从做题策略上讲我的建议是哪怕 I 版本能暴力过也最好用位独立的方法写一遍。因为这样到了 II 版本你几乎不用改代码只需要把位数上限调一调。5.2 迁移到 AND 或 XOR 版本的镜像思路如果你在周赛里碰到这道题的变体发现题目里的位运算不是按位或而是按位与或者按位异或思路依然可以迁移只是要调整“硬约束”的方向。如果是按位与bit[i] 1变成硬约束它强制a[i]和a[i 1]的那一位都是 1而bit[i] 0只要求至少有一个 0。如果是按位异或bit[i] 1表示两个位置这一位不同bit[i] 0表示两个位置这一位相同。这时候连续段的贪心规则会变成“交替填”和 OR 版本完全相反。但不管是 AND、OR 还是 XOR底层的思考路径是一样的先按位拆开弄清楚每一位上什么情况是硬约束什么情况只是“二选一”然后用从左到右的贪心去填。最后再做一次整体校验防止某一位在局部可行、合起来却矛盾的情况。5.3 一点个人建议最后分享一个我自己的习惯遇到这种“构造最小数组”的题我不会先去写代码而是先在纸上把某一层bits的所有可能形态列出来。比如[1]填[0, 1][1, 1, 1]填[0, 1, 0, 1][1, 0, 1]填[1, 0, 0, 1][0, 1, 0]无解。把这些小样例搞清楚代码里的每个 if 分支就都有依据了而不是靠试错凑答案。构造题的难点从来不是某个 API 不会用而是“什么时候填 0、什么时候填 1”的决策没有想清楚。把位独立和连续段填充这两个点吃透Leetcode 3314 构造最小位运算数组 I 对你来说就不再是简单题里的拦路虎而是一个可以顺手秒掉的常规题。
构造最小位运算数组：拆位贪心与按位或还原全解析
1. 先把题面翻译成人话构造最小位运算数组到底在还原什么1.1 位运算数组不是新概念就是相邻按位或的结果如果你和我一样点开 Leetcode 3314 构造最小位运算数组 I 之前以为它是个简单枚举题那读完题面大概会愣一下“最小”两个字才是全题的重心。位运算题最怕的不是不会用 | ^而是不知道在哪里用贪心、在哪里用暴力。这篇文章就把构造最小位运算数组 I 的完整思路拆开从位独立讲到连续段填充再给出一版可以直接提交的 Python 代码。适合刚刷完数组基础题、准备进阶位运算的读者如果你已经被 994 腐烂的橘子这类 BFS 题虐过换个脑子来做做构造题也挺好。先明确题目里的“位运算数组”到底是什么意思。设原数组为a长度为n。位运算数组b是这样得到的对每个下标i都有b[i] a[i] | a[i 1]也就是说b是相邻两个元素做按位或之后得到的结果数组它的长度是n - 1。题目给你b让你把a还原出来。这本质上是一道“给结果、求原因”的构造题。举个具体例子。如果n 3b [1, 3]那么可行解并不唯一a [0, 1, 3]0 | 1 11 | 3 3成立。a [1, 0, 3]1 | 0 10 | 3 3也成立。a [1, 1, 2]1 | 1 11 | 2 3还是成立。如果只要求“找一组可行解”随便填都能过。但题目偏偏要“最小”于是问题一下子从枚举变成了构造。1.2 “最小”意味着字典序最小不是数值最小数组比大小莱科德这类题目默认按字典序比。所谓字典序就是从头开始比较第一个不同的元素哪个数更小哪个数组就更小。如果第一个元素相同再比第二个依次类推。所以上面三个候选里[0, 1, 3]是最小的因为它的第一个元素是0而另外两个第一个元素都是1。这给我们的启发很直接构造的时候必须优先让a[0]尽量小然后让a[1]尽量小再让a[2]尽量小……也就是一个标准的贪心过程。但贪心不能瞎贪。你让a[0]变成0很可能把压力全部甩给a[1]如果a[1]被逼成了一个大数后面反而可能无解。所以必须先理解位运算的底层性质再决定每一步怎么填。2. 核心原理为什么每一位可以单独决定2.1 位独立把一个大问题拆成 30 个小问题位运算最容易被忽略、但最好用的性质是不同二进制位之间完全独立。a[i] | a[i 1]的第k位只由a[i]和a[i 1]的第k位决定。高位是1还是0完全不影响低位的结果。所以我们可以把b拆成一层一层的二进制位每一层单独构造一个“只含 0/1 的数组”最后再把所有层的构造结果按位或回去。举个例子。如果b [2, 3]二进制分别是10和11。那么第0层最低位的bits是[0, 1]第1层的bits是[1, 1]。两层互不干扰分别把a的对应位填好再合并就是最终答案。这个拆位思想在很多数组相关题目里都适用尤其是当题目里出现“按位与”“按位或”“按位异或”这种字眼时先问自己一句能不能把每个二进制位单独拎出来看多半是能的。2.2 0 是硬约束1 只是“至少有一个 1”在某一层里设bit[i]是b[i]的第k位a[i]和a[i 1]的第k位分别记为x[i]、x[i 1]。那么约束只有两种情况如果bit[i] 0因为按位或的结果是0说明x[i]和x[i 1]必须都是 0。这是硬性条件没有任何商量余地。如果bit[i] 1说明x[i]和x[i 1]至少有一个是1唯一禁止的情况是“两个都是 0”。所以整道题可以简化成一句话有一堆位置因为相邻的bit[i] 0被强制填成 0剩下的位置要尽量填 0但不能出现“相邻两个都是 0”这种非法状态。这比直接处理整个整数简单太多了。因为每一层只有 0 和 1 两种取值所有复杂决策都被压缩成“这里能不能填 0”。2.3 连续 1 段里的填充规则现在只看某一层。假设这一层的bits是bits [1, 1, 0, 1]bits[2] 0会强制x[2] 0、x[3] 0。于是整个数组被这个硬性 0 切成了两段左边一段bits[0]和bits[1]都是 1对应位置x[0]、x[1]、x[2]。右边一段bits[3]是 1对应位置x[3]、x[4]。在每一段内部规则只剩下一个相邻两个x不能同时为 0。这时候贪心就非常简单了第一个位置先尝试填 0因为越靠前越小。如果前一个位置已经是 0那当前位置必须填 1否则会出现“00”。如果前一个位置是 1那当前位置优先填 0。比如bits [1, 1, 1]时a的对应位长度是 4。按照上面的规则填出来是x [0, 1, 0, 1]验证一下0 | 1 11 | 0 10 | 1 1完全成立。而且它比[1, 0, 1, 0]小因为第一个位置是 0。再看一个带硬性 0 的例子。bits [1, 0, 1]bits[1] 0直接让x[1] 0、x[2] 0。左侧bits[0] 1但x[1]已经是 0所以x[0]只能填 1。右侧bits[2] 1但x[2]已经是 0所以x[3]只能填 1。最终结果是x [1, 0, 0, 1]这个例子特别能说明问题不要因为“优先填 0”就无脑给首位置填 0还要看后面有没有被硬性 0 卡住。3. 代码落地按位跑连续段和你想的暴力回溯不一样3.1 整体流程先拆位后填段最后统一验证实际写代码的时候没必要在每一位上都做复杂的可行性判断。我用的流程是固定的四步枚举二进制位k把b拆成这一层的bits。遍历bits把所有bit[i] 0的位置标成“强制填 0”也就是x[i]和x[i 1]都必须为 0。找bits里所有连续的“1 段”对每一段单独做贪心填充。所有位都填完后统一验证一遍(a[i] | a[i 1]) b[i]如果不成立就返回空数组。最后一步非常重要因为按位独立构造时某一层局部可行不代表整体一定可行。比如bits [0, 1, 0]这一层bits[0] 0让x[0]、x[1]都是 0bits[2] 0让x[2]、x[3]都是 0但中间的bits[1] 1又要求x[1] | x[2] 1这显然是矛盾的。所以必须在最后做一次整体校验把所有层叠加起来再看。3.2 Python 实现下面这版代码可以直接提交核心逻辑都在_build_segment里。from typing import List class Solution: def minBitwiseArray(self, b: List[int]) - List[int]: n len(b) 1 ans [0] * n # 按二进制位逐层处理31 位足够覆盖常见的 int 范围 for k in range(31): bits [(v k) 1 for v in b] # fixed[i] True 表示这一层里 a[i] 必须为 0 fixed [False] * n for i, x in enumerate(bits): if x 0: fixed[i] True fixed[i 1] True i 0 while i n - 1: if bits[i] 1: l i while i n - 1 and bits[i] 1: i 1 r i - 1 length r - l 2 start_zero fixed[l] end_zero fixed[r 1] seg self._build_segment(length, start_zero, end_zero) for j in range(length): if seg[j]: ans[l j] | (1 k) else: i 1 # 整体校验不能省 for i in range(n - 1): if (ans[i] | ans[i 1]) ! b[i]: return [] return ans def _build_segment(self, length: int, start_zero: bool, end_zero: bool) - List[int]: seg [0] * length for i in range(length): # 边界位置被硬性 0 卡住 if (i 0 and start_zero) or (i length - 1 and end_zero): seg[i] 0 continue # 前一个位置已经是 0当前位置必须补 1 if i 0 and seg[i - 1] 0: seg[i] 1 continue # 如果右边是强制 0且再往下填 0 会导致最后两个都是 0 if end_zero and i length - 2: seg[i] 1 continue # 其他情况优先填 0 seg[i] 0 return seg整个实现的核心其实只有三条填值规则被硬性 0 卡住的位置只能填 0。前一个是 0当前位置为了不出现“00”只能填 1。当前位置是“强制 0 端点的前一个位置”时如果填 0最后的强制的 0 会和它相邻形成“00”所以必须填 1。3.3 复杂度与为什么这版可以直接交时间复杂度是O(n * 31)因为每一层都要遍历一遍b和ans。空间复杂度是O(n)主要用来存bits、fixed和ans。这个复杂度对 I 版本来说绰绰有余。就算n到10^531 层循环也不过是三百多万次操作Python 完全跑得动。II 版本如果只是把n拉大、把数值范围拉高这版代码的思路依然成立不需要换算法。很多人看到“位运算”三个字就想上 DFS、回溯其实没有必要。这道题真正考的是能不能把位压到单层去理解能不能在连续段里做贪心。暴力枚举当然也能过小数据但那样收获不大。4. 我实际提交时踩过的坑全零数组、无解判定、位宽4.1 坑一无解时返回了半成品我先说一个最容易犯的错构造完所有二进制位之后没有做整体校验直接返回ans。问题是按位独立构造时每一层看起来都“局部正确”但合并起来可能无解。最典型的就是某一层出现了bits [0, 1, 0]这种情况。bits[0] 0强制a[0]、a[1]的这一位都是 0bits[2] 0强制a[2]、a[3]的这一位都是 0中间的bits[1] 1又要求a[1]和a[2]至少有一个 1。这根本不可能成立。如果不做最后校验ans里这一层全是 0表面上也能返回一个数组但放到(ans[i] | ans[i 1]) b[i]里一验就露馅。所以我在代码里专门加了一步全部位填完后再跑一遍原约束一旦发现不相等立刻返回空数组。4.2 坑二把首位贪心理解得太死另一个坑是只记住了“优先填 0”结果在连续 1 段里填错。比如某一层的bits [1, 1, 1]正确的最小结果是[0, 1, 0, 1]。但有人会想第一个位置优先填 0第二个位置也优先填 0结果变成[0, 0, ?]直接违反约束。还有人会把第一个位置填成 1得到[1, 0, 1, 0]虽然可行但不是最小。正确的理解是优先填 0 的前提是后面还能接得住。一旦前一个位置是 0当前位置就必须填 1否则就会出现两个连续的 0。这比“所有位置都尽量填 0”更准确。遇到右端点是强制 0 的情况还要额外往前推一步让倒数第二个位置填 1否则末尾也会出现“00”。4.3 坑三位宽不够最高位被吞掉还有一次我图省事只循环到range(30)结果某个用例里b[i]的最高位是第 30 位直接被我漏掉了。构造出来的ans在最后校验时全部对不上排查半天才发现是位宽问题。建议不要凭感觉写死一个位数可以直接取所有b[i]的最大二进制位长度max_bit max(b).bit_length() if b else 1 for k in range(max_bit): ...这样既不会漏位也不会多做无用的高位循环。如果题目里数值可能到2^31级别那就用 31 位如果按位与/异或题里可能出现负数更要格外小心Python 的负数和 C 的补码表示不太一样刷题时最好先确认数据范围。4.4 坑四数组初始化带来的额外心理负担这道题涉及的数组不多但数组初始化的习惯还是值得说一下。ans [0] * n和fixed [False] * n都是一维数组直接乘号初始化就好。有些朋友刚从二维数组、指针数组那边转过来喜欢顺手写[[0] * n]结果发现多了一层括号后面索引经常错位。其实构造题里的“累加位”操作很常见先初始化成全 0再根据每一层的贪心结果往对应位置用| (1 k)累加。不要试图直接算出一个完整整数那样反而容易在位上出错。5. 从 I 到 II同一套思路如何迁移5.1 I 和 II 的差异本质是数据规模很多时候LeetCode 的题目分成 I 和 II 两个版本I 版本数据范围小可以用更暴力的方法II 版本数据范围大必须上更优的做法。但构造最小位运算数组这题有点特别核心思路本身已经是线性复杂度所以 I 和 II 的差距不大。真正需要注意的是I 版本可能允许你直接对每个位置做一次小范围枚举比如从 0 试到当前b里的最大值再验证相邻或的结果。II 版本如果把n拉到10^5、把数值范围拉到2^31暴力枚举就完全不可行了。这时候按位拆解 连续段贪心的优势就出来了。从做题策略上讲我的建议是哪怕 I 版本能暴力过也最好用位独立的方法写一遍。因为这样到了 II 版本你几乎不用改代码只需要把位数上限调一调。5.2 迁移到 AND 或 XOR 版本的镜像思路如果你在周赛里碰到这道题的变体发现题目里的位运算不是按位或而是按位与或者按位异或思路依然可以迁移只是要调整“硬约束”的方向。如果是按位与bit[i] 1变成硬约束它强制a[i]和a[i 1]的那一位都是 1而bit[i] 0只要求至少有一个 0。如果是按位异或bit[i] 1表示两个位置这一位不同bit[i] 0表示两个位置这一位相同。这时候连续段的贪心规则会变成“交替填”和 OR 版本完全相反。但不管是 AND、OR 还是 XOR底层的思考路径是一样的先按位拆开弄清楚每一位上什么情况是硬约束什么情况只是“二选一”然后用从左到右的贪心去填。最后再做一次整体校验防止某一位在局部可行、合起来却矛盾的情况。5.3 一点个人建议最后分享一个我自己的习惯遇到这种“构造最小数组”的题我不会先去写代码而是先在纸上把某一层bits的所有可能形态列出来。比如[1]填[0, 1][1, 1, 1]填[0, 1, 0, 1][1, 0, 1]填[1, 0, 0, 1][0, 1, 0]无解。把这些小样例搞清楚代码里的每个 if 分支就都有依据了而不是靠试错凑答案。构造题的难点从来不是某个 API 不会用而是“什么时候填 0、什么时候填 1”的决策没有想清楚。把位独立和连续段填充这两个点吃透Leetcode 3314 构造最小位运算数组 I 对你来说就不再是简单题里的拦路虎而是一个可以顺手秒掉的常规题。
