1052. 爱生气的书店老板
题目描述：
给定两个数组customers和grumpy，其中customers[i]表示第i分钟来的顾客数量，grumpy[i]表示老板在第i分钟是否生气。grumpy[i] = 0表示老板不生气，这一分钟的顾客本来就满意；grumpy[i] = 1表示老板生气，这一分钟的顾客本来不满意。老板有一次技巧，可以让自己连续minutes分钟不生气。要求返回最多可以让多少顾客满意。
复盘笔记：
这道题可以拆成两部分：本来就满意的顾客，以及使用技巧后额外挽回的顾客。
如果grumpy[i] = 0，说明这一分钟老板本来就不生气，顾客天然满意，这部分一定会被计入答案。
如果grumpy[i] = 1，说明这一分钟顾客原本不满意，但如果技巧覆盖到这一分钟，就可以被额外挽回。
所以问题可以转化为：在grumpy = 1的位置中，找一个长度为minutes的连续窗口，使这个窗口内对应的customers总和最大。这个最大值就是技巧最多能额外挽回的顾客数。
代码里可以用：
s = [0, 0]其中：
s[0] = 所有本来就满意的顾客数量 s[1] = 当前窗口内可以被技巧挽回的顾客数量遍历时：
for i, (c, g) in enumerate(zip(customers, grumpy)):表示同时遍历customers和grumpy，其中i是当前下标，c是当前分钟顾客数，g是当前分钟老板是否生气。
每次执行：
s[g] += c如果g = 0，就把顾客数加到s[0]，表示本来就满意；如果g = 1，就把顾客数加到s[1]，表示当前窗口内可以被挽回。
当窗口长度达到minutes后，用当前的s[1]更新最大可挽回人数max_s1。随后窗口左端点离开，如果左端点对应的是生气状态，就从s[1]中减去那一分钟的顾客数。
最后答案就是：
s[0] + max_s1也就是：
本来就满意的顾客 + 技巧最多额外挽回的顾客class Solution: def maxSatisfied( self, customers: List[int], grumpy: List[int], minutes: int ) -> int: s = [0,0] max_s1 = 0 for i, (c, g) in enumerate(zip(customers, grumpy)): s[g] += c left = i - minutes + 1 if left < 0: continue max_s1 = max(max_s1, s[1]) if grumpy[left]: s[1] -= customers[left] return s[0] + max_s1面试时所用到的一段话解释本题的思想：
这道题我会先把答案拆成两部分：老板不生气时本来就满意的顾客，以及通过技巧额外挽回的顾客。第一部分可以直接累加；第二部分需要在所有长度为minutes的连续区间中，找到老板生气时对应顾客数总和最大的窗口。这个窗口表示技巧使用在哪段时间最划算。最后用基础满意人数加上最大可挽回人数，就是最终答案。
3679.使库存平衡的最少丢弃次数
题目描述：
给你两个整数w和m，以及一个整数数组arrivals，其中arrivals[i]表示第i天到达的物品类型（天数从1 开始编号）。
物品的管理遵循以下规则：
- 每个到达的物品可以被保留或丢弃，物品只能在到达当天被丢弃。
- 对于每一天
i，考虑天数范围为[max(1, i - w + 1), i]（也就是直到第i天为止最近的w天）：- 对于任何这样的时间窗口，在被保留的到达物品中，每种类型最多只能出现
m次。 - 如果在第
i天保留该到达物品会导致其类型在该窗口中出现次数超过m次，那么该物品必须被丢弃。
- 对于任何这样的时间窗口，在被保留的到达物品中，每种类型最多只能出现
返回为满足每个w天的窗口中每种类型最多出现m次，最少需要丢弃的物品数量。
复盘笔记：
这道题的核心是滑动窗口加计数表。我们需要维护最近w个位置中，每种事件出现了几次。如果当前事件x已经在窗口中出现了m次，那么这次到达就不能再保留，需要丢弃；否则就把它加入窗口计数。
代码里：
cnt = [0] * (max(arrivals) + 1)表示创建一个计数数组。数组下标就是事件编号，cnt[x]表示事件x当前在窗口中出现了几次。之所以要开到max(arrivals) + 1，是因为如果最大编号是5，我们需要能访问cnt[5]，而数组下标从0开始，所以长度必须至少是6。
如果当前事件要被丢弃，代码使用：
arrivals[i] = 0后面就是标准的滑窗思路了。
class Solution: def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int: cnt = [0]*(max(arrivals)+1) ans = 0 for i,x in enumerate(arrivals): if cnt[x]==m: arrivals[i]=0 ans+=1 else: cnt[x]+=1 left = i+1-w if left<0: continue cnt[arrivals[left]] -= 1 return ans面试时所用到的一段话解释本题的思想：
这道题我会用滑动窗口维护最近w个未丢弃事件的出现次数。对于当前到达的事件x，如果窗口中x的数量已经等于m，说明再保留它会超出限制，所以丢弃；否则加入计数。每轮结束时，如果窗口长度已经达到w，就把左端点移出窗口。这样可以保证计数表始终表示当前有效窗口内每种事件的出现次数。
整体复盘总结：
今天这两道题都还是滑动窗口思想，但维护的信息不一样。
1052：维护窗口内可以被技巧挽回的顾客数 到达事件丢弃：维护窗口内每种事件出现次数它们的共同点是：
窗口都有一个固定长度，每次遍历时都经历“右端点进入窗口”和“左端点离开窗口”。
滑动窗口题可以先问自己三个问题：
1. 窗口代表什么？ 2. 窗口中需要维护什么信息？ 3. 什么时候更新答案，什么时候移出左端点？今天的收获是：
滑动窗口不只是维护一个和，也可以维护计数数组、哈希表，甚至把答案拆成“固定贡献 + 窗口额外贡献”。只要能明确窗口内的信息怎么随着右进左出而更新，就可以把问题压到线性时间。