2026-02-09：使库存平衡的最少丢弃次数。用go语言，给定两个整数 w、m 和一个整数数组 arrivals（第 i 项表示第 i 天到达的物品种类，天

福大大架构师每日一题

发布于 2026-02-09 14:51:35

2026-02-09：使库存平衡的最少丢弃次数。用go语言，给定两个整数 w、m 和一个整数数组 arrivals（第 i 项表示第 i 天到达的物品种类，天数从 1 开始）。到达的每个物品可以选择保留或当日丢弃（不能在之后丢弃）。

规则要求：对于任意一天 i，考察以该天为终点、长度为 w 的时间段（即从 max(1, i-w+1) 到 i 的最近 w 天）。在任意这样的时间段内，最终保留下来的物品中，每一种类型的数量不能超过 m。如果在第 i 天保留该天到来的物品会使得该类型在该时间段内的保留数量超出 m，则该物品必须在到达当天丢弃。

目标是找到一种丢弃/保留的决策，使得满足上述所有窗口约束的前提下，被丢弃的物品总数最少，并返回这个最小丢弃数。

1 <= arrivals.length <= 100000。

1 <= arrivals[i] <= 100000。

1 <= w <= arrivals.length。

1 <= m <= w。

输入： 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。

题目来自力扣3679。

问题解决步骤分解

1. 初始化与准备

• 函数首先初始化一个空的哈希表 cnt，用于实时跟踪当前滑动窗口内各种物品类型的保留数量。哈希表的键（key）是物品种类编号，值（value）是该种类在当前窗口内的出现次数。
• 初始化丢弃计数器 ans 为 0，用于累计最终需要丢弃的物品数量。

2. 遍历每一天的物品

• 函数通过一次顺序遍历来处理每一天（索引 i 从 0 开始，对应第 i+1 天）到达的物品 x（即 arrivals[i]）。
• 对于每一天，处理逻辑分为两个主要部分：处理新到达物品和管理窗口左边界。

3. 处理新到达物品（决定保留或丢弃）

• 在物品 x 进入窗口时，代码会检查当前窗口内该物品已有的保留数量 cnt[x]。
• 决策逻辑：
- • 如果 cnt[x] 已经等于 m（即该物品在窗口内的数量已达到上限），那么新到达的这个物品 x 必须被丢弃。
  - • 丢弃操作：将 arrivals[i] 的值置为 0（这是一个关键技巧，用 0 标记该位置的物品已被丢弃，因为原物品编号都是正整数，0 不会与任何有效种类冲突）。
  - • 丢弃计数器 ans 加 1。
- • 如果 cnt[x] 小于 m，则这个新物品可以被安全地保留。此时，哈希表 cnt 中对应物品 x 的计数加 1。

4. 滑动窗口的维护（左边界物品出窗）

• 在处理好新物品后，代码需要检查是否有物品需要从当前窗口中“移出”。这是通过计算窗口的左边界索引 left 来实现的：left = i - w + 1。
• 移出逻辑：
- • 只有当 left >= 0 时，才意味着窗口已经完整（长度达到了 w），并且有物品（即第 left 天到达的物品）需要离开窗口。
- • 对于要离开窗口的物品（其种类是 arrivals[left]），无论它当初是被保留（值为正数）还是被丢弃（值被置为 0），都统一在哈希表 cnt 中将其对应种类的计数减 1。
- • 关键点：这个“出窗”操作是前瞻性的。它发生在索引为 i 的循环中，但实际上是在为下一个循环（即下一天 i+1）准备一个正确的窗口状态。因为当处理下一天 i+1 时，窗口的左边界就是 i+1-w = left+1，所以需要提前将第 left 天（即即将离开窗口的那一天）的影响移除。

5. 遍历结束与结果返回

• 当循环遍历完 arrivals 数组中的所有天数后，累计的丢弃次数 ans 就是满足所有窗口约束下的最小丢弃数量，将其作为结果返回。

复杂度分析

• 总的时间复杂度：O(n)。
- • 函数仅对长度为 n（n = len(arrivals)）的数组进行了一次顺序遍历。在遍历的每一步中，对哈希表 cnt 的查询、插入和修改操作在平均情况下都可以视为 O(1) 的时间复杂度。因此，总体时间复杂度是线性的 O(n)。
• 总的额外空间复杂度：O(n)。
- • 主要的额外空间消耗来自两个方面：
  1. 1. 哈希表 cnt：在最坏情况下，窗口内可能包含所有不同的物品类型。由于物品种类编号的范围很大（最大可达 10^5），但实际存储在 cnt 中的键的数量取决于当前窗口内出现的不重复物品种类数。窗口最大长度为 w，因此哈希表最多需要 O(w) 的空间。由于 w <= n，这部分可记为 O(n)。
  2. 2. 输入的 arrivals 数组本身被修改了，但这通常不计入“额外”空间，因为它是输入数据。如果考虑对输入数据的修改，那么算法是原地（in-place） 的，没有因此消耗额外空间。
- • 综合来看，空间复杂度主要取决于哈希表，为 O(n)。

通过上述的单次遍历和巧妙的哈希表计数管理，该算法高效地解决了问题，其核心在于实时维护窗口状态并即时做出最优的丢弃决策，确保了在满足约束的同时最小化丢弃总数。

Go完整代码如下：

package main

import (
    "fmt"
)

func minArrivalsToDiscard(arrivals []int, w, m int) (ans int) {
    cnt := map[int]int{}
    for i, x := range arrivals {
        // x 进入窗口
        if cnt[x] == m { // x 的个数已达上限
            // 注意 x 在未来要离开窗口，但由于已经丢弃，不能在离开窗口时修改 cnt
            // 这里直接置为 0，未来离开窗口就是 cnt[0]--，不影响答案
            arrivals[i] = 0// 丢弃 arrivals[i]
            ans++
        } else {
            cnt[x]++
        }

        // 左端点元素离开窗口，为下一个循环做准备
        left := i + 1 - w
        if left >= 0 {
            cnt[arrivals[left]]--
        }
    }
    return
}

func main() {
    arrivals := []int{1, 2, 3, 3, 3, 4}
    w := 3
    m := 2
    result := minArrivalsToDiscard(arrivals, w, m)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def min_arrivals_to_discard(arrivals: List[int], w: int, m: int) -> int:
    cnt = {}  # 计数器字典
    ans = 0
    
    for i, x in enumerate(arrivals):
        # x 进入窗口
        if cnt.get(x, 0) == m:  # x 的个数已达上限
            # 注意 x 在未来要离开窗口，但由于已经丢弃，不能在离开窗口时修改 cnt
            # 这里直接置为 0，未来离开窗口就是 cnt[0]--，不影响答案
            arrivals[i] = 0  # 丢弃 arrivals[i]
            ans += 1
        else:
            cnt[x] = cnt.get(x, 0) + 1
        
        # 左端点元素离开窗口，为下一个循环做准备
        left = i + 1 - w
        if left >= 0:
            left_val = arrivals[left]
            cnt[left_val] = cnt.get(left_val, 0) - 1
    
    return ans

if __name__ == "__main__":
    arrivals = [1, 2, 3, 3, 3, 4]
    w = 3
    m = 2
    result = min_arrivals_to_discard(arrivals, w, m)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

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

    for (int i = 0; i < arrivals.size(); i++) {
        int x = arrivals[i];

        // x 进入窗口
        if (cnt[x] == m) { // x 的个数已达上限
            // 注意 x 在未来要离开窗口，但由于已经丢弃，不能在离开窗口时修改 cnt
            // 这里直接置为 0，未来离开窗口就是 cnt[0]--，不影响答案
            arrivals[i] = 0; // 丢弃 arrivals[i]
            ans++;
        } else {
            cnt[x]++;
        }

        // 左端点元素离开窗口，为下一个循环做准备
        int left = i + 1 - w;
        if (left >= 0) {
            cnt[arrivals[left]]--;
        }
    }

    return ans;
}

int main() {
    vector<int> arrivals = {1, 2, 3, 3, 3, 4};
    int w = 3;
    int m = 2;

    int result = minArrivalsToDiscard(arrivals, w, m);
    cout << result << endl;

    return0;
}