题目：

题干分析：

题干为我们说明了一个类似流水线上的物品管理规定,内容拟似如下:

• 每天流水线上会下来一个产品,类型编号为arrivals[i].
• 每天的产品我们必须在当天决定选择保留或者丢弃.
• 工厂要求连续w天内下线的产品同一型号最多出现m次(可理解为库存最值),超过则当天产品必须丢弃.

算法思路：

题目已经几乎明示我们使用滑动窗口进行解题,剩下的便是使用哈希表当作类型计数器,然后直接模拟即可.

需要注意的是丢弃的商品要做好标记,不要没有计入计数滑出窗口时反倒出了窗口导致计数失灵.

实现代码：

int minArrivalsToDiscard(vector<int>& arrivals, int w, int m) {
        if (m >= w) return 0;
        unordered_map<int, int> cnt;// 计数器
        int ans = 0;

        for (int i = 0; i < arrivals.size(); ++i) {
            int x = arrivals[i];
            ++cnt[x];
            if (cnt[x] > m) {
                --cnt[x];
                ++ans;
                arrivals[i] = 0; // 标记为0,防止意外出窗口(1 <= arrivals[i])
            }
            if (i >= w - 1 && arrivals[i - w + 1]) {
                --cnt[arrivals[i - w + 1]];
            }
        }

        return ans;
    }

复杂度分析：

• 时间复杂度: 针对每个数组元素进行操作,总时间复杂度为O(n);
• 空间复杂度: 哈希表计数消耗额外空间站主体,总空间复杂度为O(k),k为arrivals数组中编号的种数.