北京
O(n)。這是解決“二進制字符串每秒轉換”問題的最優時間復雜度。給定一個只包含'0'和'1'的字符串，每秒所有子串“01”會同時替換為“10”，要求計算直到字符串中不存在“01”為止所需的秒數。你會選擇直觀的逐秒模擬，還是接受一次遍歷就得出答案的巧妙算法？
模擬派總是先動手：維護字符串，每輪掃描所有位置，遇到“01”就標記，然后批量替換，直到結束。這種做法直擊問題定義，易于驗證，但在數據規模面前顯得笨拙。設想字符串長度達到數萬，每秒鐘都可能產生大量替換，最壞情況下循環輪數可能接近原串長度，整體時間接近O(n2)。更糟糕的是，多個“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.
