题目大意：
爱生气的书店老板
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
提示：
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1052
解题思路分析：
题目要求求出最多有多少客户能够感到满意的数量，也就是在老板不生气的时间点内来店的客户数量总和。而生气时间点的客户数量不会记在结果之内。另外老板有个技能，能在x分钟内连续不生气，这是本题的关键，老板开技能的时间点至关重要，如果在这个时间段内，能够将更多的不满意变为满意，即为最优解。因此题目就转化为找到连续x区间内，不满意客户的最大数量。具体实现参照代码注释。
看下完整代码：
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
// 前缀和数组，lostUser[i]表示区间[0, i]之间不满意人数和。
int[] lostUser = new int[customers.length];
// max为X区间内最多不满意人数，maxIndex为区间终点
int max=0, maxIndex=0;
for(int i=0;i<grumpy.length;i++){
// 计算区间[0, i]之间不满意人数和（前缀和）
lostUser[i] = (i==0 ? 0 : lostUser[i-1])+(grumpy[i]==0?0:customers[i]);
// 通过前缀和计算出以i为终点的X长度区间范围内的不满意人数和
if(lostUser[i] - (i<X ? 0 : lostUser[i-X]) > max){
// 更新不满意人数最大值
max = lostUser[i] - (i<X ? 0 : lostUser[i-X]);
// 更新X区间终点下标
maxIndex=i;
}
}
int res=0; // 定义返回值。满意人数和
for(int i=0;i<grumpy.length;i++){
// 如果老板不生气或者当前为老板开技能区间
if(grumpy[i]==0 || i>maxIndex-X && i<=maxIndex){
res+=customers[i]; // 更新人数
}
}
return res;
}本题解法运行时间为3ms。
Runtime: 3 ms, faster than 85.20% of Java online submissions for Grumpy Bookstore Owner.
Memory Usage: 42.2 MB, less than 100.00% of Java online submissions for Grumpy Bookstore Owner.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1052-grumpy-bookstore-owner-解题思路分析/