Medium

题目描述

给你两个整数 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天，物品1到达；窗口中该类型出现次数不超过m，所以保留。
- 第2天，物品2到达；天数1-2的窗口正常。
- 第3天，物品1到达，窗口[1,2,1]中物品1出现两次，在限制范围内。
- 第4天，物品3到达，窗口[1,2,1,3]中物品1出现两次，允许。
- 第5天，物品1到达，窗口[2,1,3,1]中物品1出现两次，仍然有效。

没有物品被丢弃，所以返回0。

示例 2：

输入：arrivals = [1,2,3,3,3,4], w = 3, m = 2
输出：1
解释：
- 第1天，物品1到达。保留。
- 第2天，物品2到达，窗口[1,2]正常。
- 第3天，物品3到达，窗口[1,2,3]中物品3出现一次。
- 第4天，物品3到达，窗口[2,3,3]中物品3出现两次，允许。
- 第5天，物品3到达，窗口[3,3,3]中物品3出现三次，超过限制，必须丢弃。
- 第6天，物品4到达，窗口[3,4]正常。

第5天的物品3被丢弃，这是需要丢弃的最少数量，所以返回1。

约束条件：

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

解题思路

这道题目要求我们在维持滑动窗口约束的前提下，最小化丢弃的物品数量。核心思路是使用滑动窗口和哈希表来跟踪每种物品类型在当前窗口中的出现次数。

解题思路：

  1. 滑动窗口维护：使用双指针 left 和 right 来维护一个最大长度为 w 的滑动窗口。窗口代表当前考虑的天数范围。

  2. 计数跟踪：使用哈希表 count 记录当前窗口内每种物品类型的出现次数。

  3. 窗口更新策略：

    • 每次处理新的一天时，先将窗口右边界扩展
    • 如果窗口大小超过 w，则收缩左边界
    • 检查当前物品类型在窗口中的出现次数

  4. 丢弃决策：如果保留当前物品会使其类型在窗口中出现超过 m 次，则必须丢弃该物品。否则，将其计入窗口统计中。

这种贪心策略是最优的，因为我们总是尽可能保留物品，只在必须时才丢弃。通过维护精确的窗口状态，我们能够在 O(n) 时间内解决问题。

推荐解法：滑动窗口 + 哈希表，时间复杂度 O(n)，空间复杂度 O(min(w, k))，其中 k 是不同物品类型的数量。

代码实现

class Solution {
public:
    int minArrivalsToDiscard(vector<int>& arrivals, int w, int m) {
        unordered_map<int, int> count;
        int left = 0, discarded = 0;
        
        for (int right = 0; right < arrivals.size(); right++) {
            // Shrink window if it exceeds size w
            while (right - left + 1 > w) {
                count[arrivals[left]]--;
                if (count[arrivals[left]] == 0) {
                    count.erase(arrivals[left]);
                }
                left++;
            }
            
            // Check if we can keep the current arrival
            if (count[arrivals[right]] < m) {
                count[arrivals[right]]++;
            } else {
                discarded++;
            }
        }
        
        return discarded;
    }
};

class Solution:
    def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int:
        from collections import defaultdict
        
        count = defaultdict(int)
        left = 0
        discarded = 0
        
        for right in range(len(arrivals)):
            # Shrink window if it exceeds size w
            while right - left + 1 > w:
                count[arrivals[left]] -= 1
                if count[arrivals[left]] == 0:
                    del count[arrivals[left]]
                left += 1
            
            # Check if we can keep the current arrival
            if count[arrivals[right]] < m:
                count[arrivals[right]] += 1
            else:
                discarded += 1
        
        return discarded

public class Solution {
    public int MinArrivalsToDiscard(int[] arrivals, int w, int m) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        int left = 0, discarded = 0;
        
        for (int right = 0; right < arrivals.Length; right++) {
            // Shrink window if it exceeds size w
            while (right - left + 1 > w) {
                count[arrivals[left]]--;
                if (count[arrivals[left]] == 0) {
                    count.Remove(arrivals[left]);
                }
                left++;
            }
            
            // Check if we can keep the current arrival
            if (!count.ContainsKey(arrivals[right])) {
                count[arrivals[right]] = 0;
            }
            
            if (count[arrivals[right]] < m) {
                count[arrivals[right]]++;
            } else {
                discarded++;
            }
        }
        
        return discarded;
    }
}

var minArrivalsToDiscard = function(arrivals, w, m) {
    let discarded = 0;
    let kept = [];
    let count = new Map();
    
    for (let i = 0; i < arrivals.length; i++) {
        let item = arrivals[i];
        
        // Remove items outside the window
        while (kept.length > 0 && kept[0] <= i - w) {
            let oldDay = kept.shift();
            let oldItem = arrivals[oldDay];
            count.set(oldItem, count.get(oldItem) - 1);
            if (count.get(oldItem) === 0) {
                count.delete(oldItem);
            }
        }
        
        // Check if we can keep the current item
        let currentCount = count.get(item) || 0;
        if (currentCount < m) {
            // Keep the item
            kept.push(i);
            count.set(item, currentCount + 1);
        } else {
            // Discard the item
            discarded++;
        }
    }
    
    return discarded;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是 arrivals 数组的长度。每个元素最多被访问两次（一次加入窗口，一次移出窗口）
空间复杂度O(min(w, k))，其中 k 是不同物品类型的数量。哈希表最多存储窗口内的不同物品类型