题目描述
思路解析
一句话答案：LeetCode 3191 使二进制数组全部等于 1 的最少操作次数用贪心扫一遍：最左的 0 只能靠以它为首的三连翻转来救，从左到右遇 0 就翻并计数，末尾凑不出三个即无解，时间 O(n)、空间 O(1)。
翻转连续三个数，要把数组凑成全 1
给一个只含 0 和 1 的数组 nums，一次操作能任选连续的三个元素、把它们同时反转（0 变 1、1 变 0），操作次数不限。要用最少操作把整个数组变成全 1，做不到就返回 -1。题面 nums=[0,1,1,1,0,0] 答案是 3，而 nums=[0,1,1,1] 怎么翻都会留下一个 0，只能返回 -1。
操作次数不限，为什么不能把所有翻法都试一遍
操作次数不限、每一步又能落在任意连续三个位置上，可拼出的序列是指数级的，真去枚举所有序列再挑最短的，数组稍大就跑不完。搜索空间里还塞满冗余：同一处翻两次等于没翻，分支互相抵消。穷举走不通，得看清每一步'该怎么翻'其实并不自由、而是被前面结果锁死。
最左边那个 0，其实只有一种翻法能救它
把目光放到从左数第一个 0 上。能盖住它的三连窗口有好几个，可只要不是以它为最左端，窗口就必然向左伸出去、把已经弄成 1 的位置又翻回 0。而它再往左没有元素了，不破坏左侧的选择就独剩一个：以它为首、连翻它和右边两位。这一步是被逼的，没有第二种走法。既然每个 0 怎么处理都被它左边已固定的部分锁定，从左往右照此翻，总次数就压到了最少。
从左扫到右、遇 0 就翻，什么时候会翻不下去
做法很直白：指针从下标 0 往右走，遇 1 跳过、遇 0 就以它为左端翻转连续三个并计一次数。翻转会连带改动右边两位，可能又冒出新的 0，指针继续右移照常处理即可。真正会卡住的只有一种情形：扫到一个 0 时，它右边不足两个元素、下标 i 加 2 已越出数组，凑不出以它为左端的合法窗口，只能判无解、返回 -1。
把题面两组数据的翻转一步步走出来
手算这两组时老实翻整段三位、盯着数组一步步变；代码只翻右边两位是个结果等价的简写，留到末尾再说。先走 nums=[0,1,1,1,0,0]。第 0 位是 0，翻下标 0、1、2，得 [1,0,0,1,0,0]，一次。第 1 位又是 0，翻 1、2、3，得 [1,1,1,0,0,0]，两次。第 2 位是 1，跳过。第 3 位是 0，翻 3、4、5，得 [1,1,1,1,1,1]，三次。第 4、5 位都已是 1，扫完，答案 3。再走反例 nums=[0,1,1,1]：第 0 位翻出 [1,0,0,1]、一次，第 1 位翻出 [1,1,1,0]、两次，第 2 位是 1 跳过，第 3 位却又是 0，而它右边只剩不到两个数、下标加 2 等于 5 已越界，凑不出以它为左端的窗口，返回 -1。
别急着翻，先问一句右边还够不够三个
复杂度上，指针从头到尾只走一遍、每处最多一次翻转加一次判断，时间 O(n)；就地异或翻转、只用计数和下标几个变量，空间 O(1)。几处易错：翻转前先查 i 加 2 是否越界，右边不足三个还硬翻，会把本该 -1 的算成操作数；窗口必须严格贴着当前 0 的左端，套到它中间或右侧就翻坏左边已固定成 1 的位置。还有个反直觉处：参考代码只翻右边两位、没动 nums[i]，因为指针只右移不回看，这个 0 留着也不干扰后面的判断，翻不翻它答案都一样。本就全是 1 时答案 0，[0,0,0] 一次翻转搞定。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句:从左往右,谁是 0 就把从它开始的连续三个翻过来,数一次操作。为什么必须从左往右、为什么这样一定最省,下面用画面讲给你看。
起点 · 先找出所有的 0：先看这个二进制数组 [0,1,1,1,0,0]。红色标出来的是 0,我们的任务是把所有 0 都变成 1。每次操作能任选连续的三个数,把它们同时翻转,0 变 1、1 变 0。
一次操作 · 任选连续三个一起翻转：像这样框住连续的三个位置,一按开关,这三个数同时翻个面。有个关键想法:最左边那个 0,只有以它为左端的这一个框能翻到它,再往左没有数了。所以处理顺序只能从左往右,一个都躲不掉。
看第 0 位 · nums[0] = 0：指针走到第 0 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
框住 [0, 2] · 准备翻转：把框放在第 0 到第 2 位这三个数上。因为下标 i 加 2 等于 2,还落在数组里,框放得下,可以翻。
翻转完成 · 第 0 位变 1,操作数加一：开关一按,这三个数全翻了面。第 0 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 1 次。第 0 位从此定死是 1,指针放心往右挪。
看第 1 位 · nums[1] = 0：指针走到第 1 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
框住 [1, 3] · 准备翻转：把框放在第 1 到第 3 位这三个数上。因为下标 i 加 2 等于 3,还落在数组里,框放得下,可以翻。
翻转完成 · 第 1 位变 1,操作数加一：开关一按,这三个数全翻了面。第 1 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 2 次。第 1 位从此定死是 1,指针放心往右挪。
看第 2 位 · nums[2] = 1：指针走到第 2 位,这里已经是 1 了,不用管它,直接往右走。
看第 3 位 · nums[3] = 0：指针走到第 3 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
框住 [3, 5] · 准备翻转：把框放在第 3 到第 5 位这三个数上。因为下标 i 加 2 等于 5,还落在数组里,框放得下,可以翻。
翻转完成 · 第 3 位变 1,操作数加一：开关一按,这三个数全翻了面。第 3 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 3 次。第 3 位从此定死是 1,指针放心往右挪。
看第 4 位 · nums[4] = 1：指针走到第 4 位,这里已经是 1 了,不用管它,直接往右走。
看第 5 位 · nums[5] = 1：指针走到第 5 位,这里已经是 1 了,不用管它,直接往右走。
全部变成 1 · 答案 = 3：扫到头了,整个数组变成了 [1,1,1,1,1,1],全是 1。一路上一共动手 3 次,这就是最少操作次数,答案 3。
换一组 · [0,1,1,1] 能不能全变 1?：再看一个反例 [0,1,1,1]。只有开头一个 0,看着好像很好办,咱们按同样的规矩走一遍,看会遇到什么。
第 0 位是 0 · 框住 [0, 2] 翻转：第 0 位是 0,右边还够三个,框住第 0 到第 2 位翻转。
翻转后 · ans = 1：翻完第 0 位变成 1,可注意后面两位也被翻了,说不定又冒出新的 0,接着往下看。
第 1 位是 0 · 框住 [1, 3] 翻转：第 1 位是 0,右边还够三个,框住第 1 到第 3 位翻转。
翻转后 · ans = 2：翻完第 1 位变成 1,可注意后面两位也被翻了,说不定又冒出新的 0,接着往下看。
第 2 位是 1 · 跳过：第 2 位是 1,略过,继续往右。
第 3 位是 0 · 右边不足三个,卡住了：走到第 3 位,它还是 0,可它右边只剩不到两个数了,下标 i 加 2 等于 5,已经超出数组。没有以第 3 位为左端、长度为三的合法窗口;能盖住它的窗口都得从更左边伸过来,一翻就会破坏已经固定好的前缀,所以在保持前缀全 1 的前提下这个 0 变不成 1。
无解 · 返回 -1：所以这组数据没救,直接返回 -1。这也是判无解的唯一情形:某个 0 落在末尾不足三个的位置上,凑不出以它为左端的合法窗口,而任何盖住它的窗口都得从左边伸过来、又会翻坏已固定的前缀。
边界想清:全是 1 答案 0、[0,0,0] 一次搞定、[0,1,1,1] 翻着翻着末尾卡出无法消除的 0 返回 -1。
面试重点:每个 0 只能靠以它为左端的窗口在不破坏左侧前缀的前提下翻转所以贪心最优、右边不足三个即返回 -1、时间 O(n) 空间 O(1)。
参考代码
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 minOperations(self, nums: List[int]) -> int: ans = 0 for i, x in enumerate(nums): if x == 0: if i + 2 >= len(nums): return -1 nums[i + 1] ^= 1 nums[i + 2] ^= 1 ans += 1 return ans复杂度
- 时间：O(n)，n 是数组长度。指针从左到右只走一遍,每个位置最多做一次翻转和一次判断,都是常数操作,总量随长度线性增长
- 空间：O(1)，按峰值算。直接在原数组上做异或翻转,不额外开辅助数组,只用了答案计数和下标这几个变量,占用是常数
易错点
面试追问把动画讲成自己的话
追问这题为什么能用贪心,而且一定最优?
追问怎么判断无法全部变成 1?
追问复杂度是多少,能不能优化空间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题