題目描述:
設計一個資料流處理器。初始化時給定目標值 value 和連續次數 k。每次呼叫 consec(num) 加入一個數字,並判斷最近連續 k 個數字是否都等於 value。
解題思路: 維護一個計數器 count,記錄當前連續等於 value 的數字個數。每次 consec(num):
當 count >= k 時返回 true。
不需要真的儲存最近 k 個數字,只需要追蹤連續出現的次數即可。
時間複雜度:O(1) — 每次 consec 操作為常數時間
空間複雜度:O(1) — 只用常數額外空間
1. Initialize target = value, k = k, count = 0 2. consec(num): a. If num == target: count++ b. Else: count = 0 c. Return count >= k
佇列法:維護一個大小為 k 的佇列,每次加入新元素並移除最舊的。檢查佇列中所有元素是否等於 value。時間 O(1)(攤銷),但空間 O(k),完全不必要。
循環緩衝區法:用大小為 k 的陣列加上指標模擬環形佇列。同樣過度設計,計數器法更優。