LeetCode Hot100刷题日志D8

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. 什么时候更新答案，什么时候移出左端点？

今天的收获是：
滑动窗口不只是维护一个和，也可以维护计数数组、哈希表，甚至把答案拆成“固定贡献 + 窗口额外贡献”。只要能明确窗口内的信息怎么随着右进左出而更新，就可以把问题压到线性时间。