3679. 使库存平衡的最少丢弃次数#

题目描述#

给你两个整数 w 和 m，以及一个整数数组 arrivals，其中 arrivals[i] 表示第 i 天到达的物品类型。

对每一天 i，考虑天数范围 [max(0, i-w+1), i]（最近的 w 天）：在该任意长度不超过 w 的时间窗口内，每种物品类型最多只能出现 m 次。返回最少需要丢弃的物品数量，使条件成立。

示例 1：

1
输入：arrivals = [1,2,1,3,1], w = 4, m = 2
2
输出：0

示例 2：

1
输入：arrivals = [1,2,3,3,3,4], w = 3, m = 2
2
输出：1

解法思路#

核心：每天按顺序处理一个到达的物品，用定长窗口（大小 w）维护”当前约束窗口内各类型的出现次数”。关键观察：必须保证窗口内任意类型出现次数 ≤ m，超出的物品直接丢弃，因为它无论如何都满足不了条件（它及其同类型的 m+1 个物品在一个窗口内必然超过 m）。

沿用 入-更新-出 三步（窗口大小 w）：

出：先把离开窗口（i-w）的物品类型计数减 1（cnt[x] 为各类型在窗口内的出现次数）。
入/决策：处理第 i 天的物品 x：
- 若窗口内 cnt[x] 已等于 m，说明再加就超限，必须丢弃 → ans++，且不计入 cnt（丢弃品不占用窗口计数）。
- 否则保留 → cnt[x] += 1。

复杂度 O(n)，空间 O(U)（U 为类型最大值）。

逐步举例（arrivals=[1,2,3,3,3,4], w=3, m=2）：

i	出窗类型	到达类型 x	窗口内 cnt[x]	决策	cnt	ans
0	—	1	0	保留	1:1	0
1	—	2	0	保留	2:1	0
2	—	3	0	保留	3:1	0
3	1(→0)	3	1	保留	3:2	0
4	2(→0)	3	2	丢弃	3:2	1
5	3(→1)	4	0	保留	4:1	1

最终 ans = 1，与预期一致。

复杂度分析#

时间复杂度：O(n)，一次遍历。
空间复杂度：O(U)，U = max(arrivals)。

代码实现#

1
class Solution:
2
    def minArrivalsToDiscard(self, arrivals: list[int], w: int, m: int) -> int:
3
        max_val = max(arrivals)
4
        cnt = [0] * (max_val + 1)
5

6
        ans = 0
7
        for i, x in enumerate(arrivals):
8
            if i >= w:
9
                cnt[arrivals[i - w]] -= 1
10

11
            if cnt[x] >= m:
12
                ans += 1
13
            else:
14
                cnt[x] += 1
15

16
        return ans

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6
from solution import Solution
7

8

9
class TestMinArrivalsToDiscard(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        arrivals = [1, 2, 1, 3, 1]
15
        w = 4
16
        m = 2
17
        self.assertEqual(self.solution.minArrivalsToDiscard(arrivals, w, m), 0)
18

19
    def test_example2(self):
20
        arrivals = [1, 2, 3, 3, 3, 4]
21
        w = 3
22
        m = 2
23
        self.assertEqual(self.solution.minArrivalsToDiscard(arrivals, w, m), 1)
24

25
    def test_all_same_type(self):
26
        arrivals = [1, 1, 1, 1, 1]
27
        w = 3
28
        m = 2
29
        # i=0: keep 1, cnt[1]=1
30
        # i=1: keep 1, cnt[1]=2
31
        # i=2: keep 1, cnt[1]=3 → wait, remove i=0? no, i=2 < w=3
32
        # Actually i=0,1,2: no removal yet. cnt[1]=3 > m=2 at i=2? No, at i=0 cnt=1, i=1 cnt=2, i=2 cnt=3 - but i=2 < w=3 so no removal
33
        # At i=2: cnt[1]=2 before adding, so cnt[1] < m=2? No, cnt[1]=2 which is not < 2, so cnt[1] >= m, discard
34
        # Hmm, let me re-trace
35
        # i=0: cnt[1]=0 < 2, keep, cnt[1]=1
36
        # i=1: cnt[1]=1 < 2, keep, cnt[1]=2
37
        # i=2: cnt[1]=2 >= 2, discard, ans=1
38
        # i=3: remove i=0 (1), cnt[1]=1. cnt[1]=1 < 2, keep, cnt[1]=2
39
        # i=4: remove i=1 (1), cnt[1]=1. cnt[1]=1 < 2, keep, cnt[1]=2
40
        # ans=1
41
        self.assertEqual(self.solution.minArrivalsToDiscard(arrivals, w, m), 1)
42

43
    def test_w_equals_one(self):
44
        arrivals = [1, 2, 1, 2]
45
        w = 1
46
        m = 1
47
        # Each window is just the current day, so each type can appear at most once
48
        # i=0: keep 1, cnt[1]=1
49
        # i=1: remove i=-1? no. cnt[2]=0 < 1, keep, cnt[2]=1
50
        # i=2: remove i=1 (2), cnt[2]=0. cnt[1]=0 < 1, keep, cnt[1]=1
51
        # i=3: remove i=2 (1), cnt[1]=0. cnt[2]=0 < 1, keep, cnt[2]=1
52
        self.assertEqual(self.solution.minArrivalsToDiscard(arrivals, w, m), 0)
53

54
    def test_all_discard(self):
55
        arrivals = [1, 1, 1]
56
        w = 2
57
        m = 1
58
        # i=0: keep 1, cnt[1]=1
59
        # i=1: cnt[1]=1 >= 1, discard, ans=1
60
        # i=2: remove i=0 (1), cnt[1]=0. cnt[1]=0 < 1, keep, cnt[1]=1
61
        self.assertEqual(self.solution.minArrivalsToDiscard(arrivals, w, m), 1)
62

63
    def test_large_m(self):
64
        arrivals = [1, 2, 3, 4, 5]
65
        w = 5
66
        m = 10
67
        self.assertEqual(self.solution.minArrivalsToDiscard(arrivals, w, m), 0)
68

69

70
if __name__ == "__main__":
71
    unittest.main()