企业官网建设流程全解析

LeetCode 1419 这道“数青蛙”的题，我刷了好几遍，每次看都有点新的感觉。光看题目名，很多人会觉得又是字符串暴力匹配，实际上它是一道很典型的“状态机 + 并发峰值”问题，核心是判断一堆打乱的 “croak” 字符序列是否合法，同时算出最少需要几只青蛙才能把整段叫声发出来。这里单独把“内存 100%”拿出来讲，是因为这道题完全可以用只用几个整型变量的解法，把额外的内存开销压到接近零，在提交记录里内存表现经常能排到 100%。文章会把题目拆开、把状态机的思路讲透，再把能直接抄的代码和排坑经验一起放出来。

1. 题目拆解：先搞清楚它到底在问什么

1.1 从一条鸣叫说起：croak 到底是什么规定

题目会给一个字符串，里面只有c、r、o、a、k这五种字符。一只青蛙叫一遍“croak”的时候，必须按这个顺序发出五个音，少一个不行，顺序乱了也不行。

但难点在于，字符串是很多只青蛙一起叫的时候录下来的结果。不同青蛙的叫声可以交错，比如第一只青蛙刚发出c，第二只青蛙就已经开始发出下一个c；之后第一只青蛙继续发r，第二只青蛙也发它的r。你需要在这样一堆嘈杂的字符里判断：这段录音到底能不能由若干只青蛙各按顺序叫完一整遍“croak”拼出来？如果能，最少需要几只青蛙？

举几个例子感受一下：

这里最容易错的就是第二行。croakcroak并不是两只青蛙同时叫，而是一只青蛙叫完一遍之后，再从头叫一遍，所以答案是 1。这说明“最少青蛙数”不是简单数出现了几遍croak，而是要看同一时刻最多有几段没叫完的声音。

1.2 最少青蛙的等价转化：看同一时刻的并发数

想象你在操场上听一群青蛙叫。每只青蛙一次只能发一个音，而且必须按照c、r、o、a、k的顺序一个音一个音往后走。某个瞬间如果同时有 3 段叫声卡在不同阶段没结束，那至少得有 3 只青蛙在场。

反过来想：如果某个瞬间最多只有 2 段未完成的叫声，那 2 只青蛙一定够吗？答案是够。因为当一段叫声走到k结束之后，那只青蛙就空闲了，可以立刻开始下一段叫声。只要每个时刻的并发数不超过 2，我们就永远能在新的c出现时找到一只空闲青蛙。

所以这道题的核心就变成一个很单纯的指标：扫描整个字符串的过程中，同时保持“未完成”状态的叫声数量最大值是多少，答案就是多少。

这也解释了为什么很多人一开始写“统计五个字符出现次数是否相等”的做法会挂掉。比如"ccroakroak"，各个字符数量看似能对上，但第二个c出来的时候前一个c还没推进到r，顺序结构根本没法匹配，最后会提前终止在某一步，返回 -1。

1.3 非法输入的主要形态

要提前想清楚哪些字符串一定不合法，这对接下来的代码很重要。大体上有这几类：

• 长度不是 5 的倍数。一段完整叫声贡献 5 个字符，合法字符串的总长度必然是 5 的倍数。
• 某个字符出现时，前置状态还没有准备好。比如直接来了个r，但前面没有发生过c。
• 字符串走完后还有叫声没叫完。比如最后停在a阶段，青蛙只叫到一半就结束了。
• 某个字符的计数在中间就出现倒挂。比如r的数量超过了c的数量，说明有不讲道理的r。

2. 核心解题思路：把“青蛙叫”当成一条流水线

2.1 五阶段状态机建模

很多人一听到状态机就觉得抽象，其实这里可以理解成一条流水线，青蛙的叫声分五个工位：

1. 发出c，进入工位 1。
2. 发出r，从工位 1 进入工位 2。
3. 发出o，从工位 2 进入工位 3。
4. 发出a，从工位 3 进入工位 4。
5. 发出k，从工位 4 下线，整段叫声结束。

我只需要维护四个变量，分别表示当前有多少段叫声正卡在c、r、o、a这四个未完成阶段。每个字符读进来时，要么开启一条新流水线，要么把一条已有流水线往后推一格。

用生活化的比喻：你在餐厅排队点餐，每个订单要经过“点单→配菜→烹饪→出餐”四个步骤。某顾客走到哪一步，你就往对应的队列里记一笔。当一位顾客完成出餐时，就把这个订单从队列里划掉。这里要统计的是同一时刻餐厅里最多同时有多少份订单尚未完成。

2.2 为什么不需要记录具体是哪只青蛙在叫

我见过不少人一开始想把每只青蛙分配出来：碰到c就开一只青蛙，碰到k就让这只青蛙休息。这样也能做，但会陷入很多无谓的细节。

比如你可以开一个队列存当前空闲青蛙的编号，每个c来的时候 pop 一个，每个k来的时候 push 回去。这种方法不错误，但完全没必要。我们关心的是并发数的峰值，至于某个时刻具体是哪只青蛙在叫第几声，根本不影响最小数量的计算结果。

只要保证“每个新出现的c都能对应一条刚开始的叫声，且这段叫声最终会在某一刻遇到自己的k结束掉”，就足够了。所以在状态机里，我只记录有多少段叫声停在某个阶段，而不是这些叫声分别属于谁。

2.3 从数组到五个变量：内存优化的契入点

一个自然的实现是用一个长度为 5 的数组cnt[5]，下标 0 到 4 分别对应c、r、o、a、k。这样代码写起来很对称，也不容易错。

但题目标题里提到的“内存 100”，正是从这之后走出来的。我最后选择的实现里，数组也不需要，直接定义 4 个整型变量就够了。为什么这里连k的计数也不需要？因为一段声音在发出k的那一刻就结束了，它不会再占用任何“未完成状态”，所以不需要把它留在计数器里。

如果把五个元素变成一个固定长度的数组，内存仍然是 O(1)，但标题里强调的“内存 100”更偏向于极致：连数组分配都免掉，只用栈上的几个局部变量。这种差异在 Python 里尤其明显，因为列表对象的创建会带来运行时开销和 GC 压力，而几个整数变量的分配几乎可以忽略不计。

3. 内存 100% 的实现细节

3.1 完整代码先放出来

下面这个版本是我实际用的，时间复杂度和空间复杂度都压到了最低：

class Solution: def minNumberOfFrogs(self, croakOfFrogs: str) -> int: if len(croakOfFrogs) % 5 != 0: return -1 c = r = o = a = 0 active = 0 ans = 0 for ch in croakOfFrogs: if ch == 'c': c += 1 active += 1 if active > ans: ans = active elif ch == 'r': if c == 0: return -1 c -= 1 r += 1 elif ch == 'o': if r == 0: return -1 r -= 1 o += 1 elif ch == 'a': if o == 0: return -1 o -= 1 a += 1 else: # 'k' if a == 0: return -1 a -= 1 active -= 1 return ans if active == 0 else -1

这段代码的逻辑可以用一句话概括：遇到k前，每次读到一个字符都让对应的前一个阶段减少一个，并让当前阶段增加一个；读到k时，把整个处于尾声的叫声从进行中状态里移除。

3.2 逐分支解释：为什么要这样转移

挨个看几个分支的原理：

• c分支：说明一只青蛙刚刚张开了嘴，开始叫这一遍。它进入“已发c”的状态，同时进行中的叫声数量active加一。ans在这里更新就够了，因为只有新c出现才可能让并发数量增加。
• r分支：必须有至少一段叫声已经发过c，否则这个r是孤儿。找到一段卡在c状态的叫声，让c减一、r加一。整个过程中这段叫声仍然是未完成状态，所以active不变。
• o、a分支同理，分别检查前一个状态的计数是否大于 0。
• k分支：必须有处于a状态的叫声。读到k时，这段叫声补完了最后一个音，立即结束，所以a减一，active减一。这里没有k计数器，因为结束后这段叫声从“未完成”集合里退出，不再参与任何后续匹配。

这里有个很关键的细节：为什么k分支只看a，而不去管active里其他类型的叫声？因为一段叫声从c开始到k结束，中间不管卡在哪个阶段，active都保持计数。只有k落地的瞬间，整个叫声才正式完结。所以k分支里a必须是正的，表示确实有一句叫到了最后一个音前。

3.3 用一张过程表走一遍复杂样例

拿"crcoakroak"举例，完整走一遍看每个变量变化：

最终active归零，返回ans = 2，答案正确。

再走一个非法样例"croakcroa"：

前五步正常完成第一句：c=0, r=0, o=0, a=0, active=0。然后第二句走到了c r o a，结束后active = 1，因为最后少了k，函数末尾检查active == 0失败，返回 -1。

这说明结束时的active == 0不是可有可无的装饰，它是判断“声音全部叫完”的重要防线。

4. 正确性与复杂度分析

4.1 为什么这样算出来就是最少的青蛙数

从两个方向证明一下。

先证明“不会少于峰值”。假设扫描到某个位置时，同时有P段叫声没有结束。每段未结束的叫声必须由一只独立的青蛙来发，因为同一只青蛙在同一时刻只能发一个音。所以需要的青蛙数至少是P。而ans取的是所有时刻里P的最大值，那么最终ans就是所需青蛙数的一个下界。

再证明“存在只用ans只青蛙完成的安排”。因为任意时刻的并发数都不超过ans，我们可以准备ans只青蛙，给它们编号。每当字符串里的c出现时，从空闲青蛙里挑一只来发；当某个叫声走到k时，那只青蛙重新回到空闲池。由于任意时刻需要的空闲青蛙数量不会超过ans，这个分配过程永远不会出现“青蛙不够用”的情况。所以ans也是可行的。

上下界碰到一起，答案就是ans。

这种“找最大并发数”的思想，其实在很多调度类题目里都有应用。你不需要真的把每只青蛙的名字记下来，只需要知道某个时间窗口内同时存在多少个无法分割的任务实体。

4.2 时间与空间复杂度

• 时间复杂度：O(n)，其中 n 是字符串长度。整个字符串只需要从头到尾扫描一遍，每个字符只做常数次判断和整数加减。
• 空间复杂度：O(1)。只用了c、r、o、a、active、ans这六个整数变量，没有使用任何和 n 相关的存储结构。

这在 LeetCode 上属于非常理想的情况，尤其是字符串长度很大的时候，不会有任何额外的内存膨胀。

4.3 内存 100% 的真相：别被百分比冲昏头脑

这里的“内存 100”，放到 LeetCode 的提交记录里，并不是一个绝对的保证。不同语言、不同运行环境的评测结果会有波动，有时候你同一份代码提交一次排 80%，第二次排 100%。但用五个整型变量取代数组、字典、列表，确实把内存占用压到了理论最低值。

以 Python 为例，int类型的对象本身存在，但几个小整数在解释器里往往会被缓存复用，实际开销远小于创建一个 list 或 dict。用数组cnt[5]其实大多数情况也是 O(1) 内存，但分配一个新列表对象时，会多出一次堆内存操作，而直接使用变量避免了这次分配。

从工程角度看，这种差异在 10 万级以下的字符串上几乎不会影响执行时间，但作为刷题优化，知道“可以只用变量”这件事本身就是一种提升。把代码从“能用”优化到“尽量省”，也是对自己代码洁癖的一种训练。

5. 常见错误与排查笔记

5.1 错误一：只统计字符总数，不检查顺序

有人看到题目就觉得，统计c、r、o、a、k出现的次数，如果完全相等就返回最大并发数。但是"ccrrooaakk"这样构造的字符串，字符总数完全相等，真实含义却是所有青蛙都在先叫c，再叫r，最终没法拼成合法叫声。状态机里的前置计数检查，就是为了拦住这种顺序混乱的情况。

一旦出现“后一个状态的计数大于前一个状态的计数”，就必须立刻返回 -1，而不是继续扫下去。

5.2 错误二：忘了检查整体是否叫完

我见过最多的问题是：把ans求出来之后，直接返回ans。比如"croakcroa"，整个流程扫完，前一半完成了，后一半停在a阶段。如果只看ans，算出来是 1，但真实答案应该是 -1，因为有一只青蛙叫了一半就停了。

所以最后一定要检查active == 0。只有当所有开始的声音都走到了k并结束，整个字符串才是合法录音。

5.3 错误三：过度设计，给每只青蛙分配状态

有些解法会维护一个数组，记录每只青蛙当前叫到哪个阶段，然后模拟着往里面填。这就像为了统计停车场同时停了多少辆车，非要给每辆车编一个车牌号再去查。实际只需要统计“当前停车场里总共停了几辆车”，峰值就是答案。

给每只青蛙分配身份会引入大量不必要的状态转移逻辑，而且容易在字符串很长时造成空间浪费。使用并发峰值思路后，代码会变得非常干净。

5.4 错误四：用k计数去搞“复用”

还有一类做法是，遇到c时去看k的计数，如果k大于 0 就把k减一，表示重用一只已经叫完的青蛙。这种做法也能算出正确答案，但思路绕了一点。它把“回收青蛙”这个动作显式建模了，而我们的状态机里，回收动作是隐式完成的：k出现时active减一，下次c出现时active加一，自然就复用了。

所以简化后的代码根本不需要k这个变量。

5.5 一个快速自测的样例集

写完代码后，可以把下面这些用例跑一遍：

输入 预期输出 croak 1 croakcroak 1 crcoakroak 2 croakcroakcroak 1 crock -1 croakcroa -1 crrak -1

如果这些全过了，再补一个大字符串压力测试，确认没有超时。一个 10 万字符的合法字符串应该瞬间返回。

6. 写在最后：一点个人体会

这道题我前后至少写过三个版本。第一版用字典统计每个字母出现的位置，第二版用队列模拟每只青蛙的叫声状态，第三版才收敛到上面这个最干净的状态机。做完之后最大的体会是，很多看起来复杂的字符串模拟题，本质上都在问同一件事：你能否把过程抽象成几个状态，并追踪关键状态的峰值。这比单纯堆数据结构重要得多。

如果你在面试里碰到这题，完全可以在讲完思路之后，顺手提一句“这个实现只用几个变量，不需要额外的存储结构”。这种对复杂度的敏感，往往比写出一个能跑的版本更让面试官眼前一亮。

最后再分享一个小技巧：刷这种题时，别急着写代码，先在草稿纸上模拟一遍"crcoakroak"，把每个阶段的计数变化写出来。只要手动推一遍，你就不会再看漏active的增减逻辑。之后再看任何类似的“匹配顺序 + 并发计数”题目，都能快速套上这个框架。