题目描述
思路解析动画文字版
记牢一句话:差值遇 L 加一、遇 R 减一,只要差值回到 0 就收下一个平衡段。下面每一帧都在套这句。
总览 · 计数器清零,从最左边开扫：上面这排是 "LRLRLLRRLR" 拆开的 10 个字符,前面有交错,中间也会出现连续的 L 和 R。开扫前把差值计数器清成 0,它代表「目前 L 的个数减 R 的个数」。从最左边第 0 个字符开始,一个一个往右看,差值一回到 0 就收下一段。
读第 0 个 · "L"：扫到第 0 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 1 个 · "R"：扫到第 1 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 1 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 1 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 1 段,这段(变蓝)收走,下一段从第 2 位重新开始数。
读第 2 个 · "L"：扫到第 2 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 3 个 · "R"：扫到第 3 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 2 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 3 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 2 段,这段(变蓝)收走,下一段从第 4 位重新开始数。
读第 4 个 · "L"：扫到第 4 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 5 个 · "L"：扫到第 5 位,是 "L",差值加一,现在差值是 2。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 2,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 6 个 · "R"：扫到第 6 位,是 "R",差值减一,现在差值是 1。绿色是当前还没收走的这一段。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 7 个 · "R"：扫到第 7 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 3 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 7 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 3 段,这段(变蓝)收走,下一段从第 8 位重新开始数。
读第 8 个 · "L"：扫到第 8 位,是 "L",差值加一,现在差值是 1。绿色这一段是从上一段结尾到这里、还没收走的部分。
暂不成段 · 差值还没归零：差值是 1,不等于 0,说明这一段里 L 和 R 还没配齐,现在收下两边不平衡。所以先不收,把这一位并进当前这段(红框),继续往右扫。
读第 9 个 · "R"：扫到第 9 位,是 "R",差值减一,现在差值是 0。绿色是当前还没收走的这一段。
第 4 段成型 · 收下：差值回到 0 了,说明从上一段结尾到第 9 位这一段里,L 和 R 一样多,是个完整的平衡段。收下这一段,段数变成 4 段,这段(变蓝)收走,下一段从第 10 位重新开始数。
完成 · 答案 4 段：10 个字符全扫完,差值正好停在 0,整串被切成 4 段:开头两段各是一个 "LR",中间攒出一个 "LLRR",最后又一个 "LR"。每段 L 和 R 都一样多,段数最多就是 4,答案站得住。
边界都一个套路:差值每归零一次就多一段;像 "LLLLRRRR" 中途从不归零,只能当一整段。
面试重点:能切就切所以最优、计数方向不影响结论、时间 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 balancedStringSplit(self, s: str) -> int: ans = l = 0 for c in s: if c == 'L': l += 1 else: l -= 1 if l == 0: ans += 1 return ans复杂度
- 时间：O(n)，n 为字符串长度。从左到右每个字符只看一遍,做一次加减和一次「是否归零」判断,整体是线性扫描
- 空间：O(1)，自始至终只用了差值计数器和段数计数器两个整数,没有额外的数组或栈,峰值占用是常数
易错点
面试追问把动画讲成自己的话
追问为什么贪心每次差值归零就切,一定能得到最多的段数?
追问计数器记「L 的个数减 R」和记「R 减 L」有区别吗?
追问这题的时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
使每位学生都有座位的最少移动次数
LeetCode 2037 · 简单 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题