北京
O(n)。这是解决“二进制字符串每秒转换”问题的最优时间复杂度。给定一个只包含'0'和'1'的字符串，每秒所有子串“01”会同时替换为“10”，要求计算直到字符串中不存在“01”为止所需的秒数。你会选择直观的逐秒模拟，还是接受一次遍历就得出答案的巧妙算法？
模拟派总是先动手：维护字符串，每轮扫描所有位置，遇到“01”就标记，然后批量替换，直到结束。这种做法直击问题定义，易于验证，但在数据规模面前显得笨拙。设想字符串长度达到数万，每秒钟都可能产生大量替换，最坏情况下循环轮数可能接近原串长度，整体时间接近O(n²)。更糟糕的是，多个“1”之间的互相阻塞会使模拟的轮数远超直觉预期，内存中对字符串的频繁重写也让性能雪上加霜。
优化派则抓住一个本质：每个“1”最终都要向左穿越它前面的所有“0”。如果只是确认最终位置，似乎每个“1”需要的秒数就等于它前方“0”的个数——但问题在于，“1”不能相互超越，它们必须排队通行。这种排队带来的延迟，恰恰是理解O(n)解法的关键。
在线性扫描算法中，我们只维护两个变量：zeros记录当前已遍历的“0”的个数，time则是处理到当前位置时所需的累积秒数。从头开始逐个字符扫描：遇到“0”就递增zeros；遇到“1”且zeros大于0时，利用公式 time = max(time + 1, zeros) 更新time。最终得到的time就是答案。遍历一遍，时间复杂度O(n)，空间仅用了两个整型变量，堪称极致。
初看这段代码，多数人会立即抛出几个问题：zeros到底在积累什么？为什么只在遇到“1”时才更新time？又为什么更新时用max(time+1, zeros)这么曲折的方式，而不是直接time = zeros？time+1代表着什么？为什么这个线性扫描能避免模拟每一秒？让我们逐个拆解。
zeros作为一个计数器，它的真实含义是“当前已出现、但尚未被某个'1'彻底跨越的'0'的数量”。在遍历过程中，每当碰到一个“0”，意味着未来会有“1”需要从它上面越过，所以计数增加。直到某个“1”真的开始移动并最终通过它，这种“待跨越”的状态才会消除。
但在算法里我们并不显式扣减zeros，因为最终答案已经交织在time中。实际上，zeros会在整个遍历过程中持续增加，因为它后面的“0”对更后面的“1”来说，仍然是障碍物。zeros只积累不减少，却不会导致time失真，正是因为time通过max动态权衡了排队与障碍两股力量。
time代表当前已处理的“1”完成全部移动所需的最少秒数。第一个“1”出现时，没有任何前面“1”的阻挡，它只需要跨过此前积累的所有zeros个“0”，所以理论上time=zeros。但随后每个新“1”的加入，情况就变得不同了：它既要跨过自己前面的“0”，又要尊重前面“1”的移动节奏——因为所有“1”在每秒内都只能整体将每个“0”向左推一个位置，“1”之间不能穿行。
这就引出了time+1的含义：当一个新的“1”准备出发时，它必须排在最近一个“1”完成全部移动的时刻之后再加1秒。因为它至少需要比前一个“1”晚1秒才能开始移动（否则就穿过了前车）。但与此同时，它自己的障碍物数量也可能很大：如果前面堆积的zeros足够多，跨越这些0本身就需要zeros秒，可能大于time+1。所以实际需要的秒数取两者中的最大值：time = max(time + 1, zeros)。
当zeros较少而排队阻塞严重时，time+1会主导更新，体现串行等待；当zeros很多而排队相对宽松时，zeros直接接管，体现跨越障碍的硬需求。这种二选一的逻辑，把逐秒模拟中繁琐的“碰撞检测”压缩为一次max判断。一次遍历结束时，time就是全局答案，全程无需真实模拟任何一秒，因为每个“1”的最终时刻已经被公式精确推演出来。这正是O(n)解法的精髓，也是那个max公式让人一再回味的原因。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
