MediumRating 1444

2526. Find Consecutive Integers from a Data Stream

hash-tabledesignqueuecountingdata-stream

解題說明

題目描述：設計一個資料流處理器。初始化時給定目標值 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 的陣列加上指標模擬環形佇列。同樣過度設計，計數器法更優。

Find Consecutive Integers from a Data Stream — CaffeCode