LeetCode 3679. 平衡庫存的最少丟棄次數（貪心＋滑動視窗圖解）

3679. 平衡庫存的最少丟棄次數

題目描述

給你兩個整數 w 和 m，以及一個整數陣列 arrivals，其中 arrivals[i] 表示第 i 天到達的物品類型（天數從 1 開始編號）。

物品的管理遵循以下規則：

• 每個到達的物品可以被保留或丟棄，物品只能在到達當天被丟棄。
• 對於每一天 i，考慮天數範圍為 [max(1, i - w + 1), i]（也就是直到第 i 天為止最近的 w 天）：
  • 對於任何這樣的時間窗口，在被保留的到達物品中，每種類型最多只能出現 m 次。
  • 如果在第 i 天保留該到達物品會導致其類型在該窗口中出現次數超過 m 次，那麼該物品必須被丟棄。

回傳為滿足每個 w 天的窗口中每種類型最多出現 m 次，最少需要丟棄的物品數量。

範例 1

輸入：arrivals = [1,2,1,3,1], w = 4, m = 2
輸出：0
解釋：每個窗口內物品 1 最多出現兩次，符合限制，沒有任何物品被丟棄。

範例 2

輸入：arrivals = [1,2,3,3,3,4], w = 3, m = 2
輸出：1
解釋：
- 第 4 天，窗口 [2, 3, 3] 中物品 3 出現兩次，允許。
- 第 5 天，窗口 [3, 3, 3] 中物品 3 出現三次，超過限制，因此該物品必須被丟棄。
- 第 6 天，窗口 [3, 4] 是可以的。
第 5 天的物品 3 被丟棄，這是最少必須丟棄的數量，所以回傳 1。

限制

• 1 <= arrivals.length <= 10^5
• 1 <= arrivals[i] <= 10^5
• 1 <= w <= arrivals.length
• 1 <= m <= w

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解為自行補充。

原題文中有一句要求建立名為 caltrivone 的變數來儲存輸入，屬於題目的出題限制，與演算法無關，本文省略。

前置知識：定長滑動視窗與出現次數表

定長視窗每次右移一格，少一個最左元素、多一個新元素，用雜湊表（或陣列）cnt 記錄視窗內每個元素的出現次數：進來加一、出去減一。前幾篇已經用過，例如 2841 和 2461。

思路

貪心：晚丟比早丟好

當物品 x = arrivals[i] 進入視窗時，如果發現視窗中 x 的出現次數會超過 m，有兩種選擇：

1. 丟棄剛進入視窗的 x。
2. 如果視窗中還有另一個同類型的 x'，時光倒流到 x' 進入視窗的那一刻，把 x' 丟掉。

哪種更好？晚丟更好。如果後面還有更多的 x，晚丟會讓視窗中 x 的個數比早丟更少，後面需要丟棄的物品也就更少。所以規則很簡單：一超過上限，就丟剛進來的那一個。

定長滑動視窗

注意一開始長度為 1, 2, 3, …, w − 1 的視窗也要檢查是否需要丟棄。

用雜湊表 cnt 統計視窗中每種物品（已保留的）的出現次數。

物品 x = arrivals[i] 進入視窗時：

• 如果 cnt[x] == m，丟棄 x，答案加一。
• 否則 cnt[x] 加一。

物品 x = arrivals[i + 1 - w] 離開視窗時：cnt[x] 減一。

易錯點：被丟棄的物品未來離開視窗時，不能再減 cnt，因為它從來沒加進去。做法可以是用布林陣列標記已丟棄，或像題解那樣直接把 arrivals[i] 改成 0（題目中物品類型 ≥ 1），之後離開視窗時只會減到 cnt[0]，不影響判斷。

圖解（可互動）

用範例 2：arrivals = [1,2,3,3,3,4]，w = 3，m = 2。第 5 天物品 3 進來時，cnt[3] 已經是 2，所以被丟棄；接著看第 3 天的 3 離開視窗時，cnt[3] 正確減回 1，而被丟棄的那個 3 離開時不會影響 cnt。

上一步 下一步 重置

arrivals = [1,2,3,3,3,4]，w = 3，m = 2

窗口（最近 w 天） 被丟棄的物品 入 = 今天到達 出 = 本步結束後離開窗口

已丟棄 ans0

窗口內保留的物品數0

解法（灵茶山艾府）

class Solution {
    public int minArrivalsToDiscard(int[] arrivals, int w, int m) {
        Map<Integer, Integer> cnt = new HashMap<>(); // 更快的寫法是用陣列
        int ans = 0;
        for (int i = 0; i < arrivals.length; i++) {
            int x = arrivals[i];
            // x 進入視窗
            int c = cnt.getOrDefault(x, 0);
            if (c == m) { // x 的個數已達上限
                // 注意 x 在未來要離開視窗，但由於已經丟棄，不能在離開視窗時修改 cnt
                // 這裡直接置為 0，未來離開視窗就是 cnt[0]--，不影響判斷條件
                arrivals[i] = 0; // 丟棄 arrivals[i]
                ans++;
            } else {
                cnt.put(x, c + 1);
            }

            // 左端點元素離開視窗，為下一個迴圈做準備
            int left = i + 1 - w;
            if (left >= 0) {
                cnt.merge(arrivals[left], -1, Integer::sum); // cnt[arrivals[left]]--
            }
        }
        return ans;
    }
}

複雜度分析

• 時間複雜度：O(n) 或 O(n + U)，其中 n 是 arrivals 的長度，U = max(arrivals)。
• 空間複雜度：O(n) 或 O(n + U)。