[LintCode] 1849. Grumpy Bookstore Owner

There is a bookstore. In the next n days, customer[i] customers will arrive on the i-th day and leave at the end of that day.

However, the bookstore owner's temper is sometimes good but sometimes bad. We use an array of grumpy to indicate his temper is good or bad every day. If grumpy[i]=1, it means that the owner's temper is very bad on the day of ii. If grumpy[i]=0, it means that the owner has a good temper on the first day.

If the owner of the bookstore has a bad temper one day, it will cause all customers who come on that day to give bad reviews to the bookstore. But if one day you have a good temper, then all customers will give the bookstore favorable comments on that day.

The boss wanted to increase the number of people who gave favorable comments to the bookstore as much as possible and came up with a way. He can keep a good temper for X days in a row. But this method can only be used once.

So how many people in this bookstore can give favorable comments to the bookstore when they leave on this n day?

• 1 ≤ X ≤ customers.length = grumpy.length ≤ 20000
• 0 ≤ customers[i] ≤1000
• 0 ≤ grumpy[i] ≤ 1

Example 1:

Input:
[1,0,1,2,1,1,7,5]
[0,1,0,1,0,1,0,1]
3
Output: 
16
Explanation: 
The bookstore owner keeps themselves not grumpy for the last 3 days. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

有一个书店，在接下来的 n 天中的第 I 天会有 customer[I] 个顾客到来，并且在这一天结束后离开。

但是书店老板的脾气时好时坏，我们用一个数组 grumpy 表示他每一天的脾气好坏，若 grumpy[i]=1, 则表示第 i 天老板的脾气很不好；若 grumpy[i]=0, 则表示第 i 天老板的脾气很好。

若某一天书店老板的脾气不好，则会导致所有当天来的所有顾客会给书店差评。但如果某一天脾气好，那么当天所有顾客都会给书店好评。

老板想要尽量增加给书店好评的人数数量，想了一个方法。他可以保持连续X天的好脾气。但这个方法只能使用一次。

那么在这 n 天这个书店最多能有多少人离开时给书店好评？

这道题的思路是双指针/滑动窗口，不过这道题的窗口的大小是固定的，为 X。

题目说老板可以最多保持 X 天不发火，那么我们可以对 input 数组的头 X 个元素进行计算，假设老板可以在这头 X 天内不发火。此时我们可以得到一个用户的好评，这一段的分数很好计算，我们记为 sum。从 X + 1 天开始（index == X），我们每往右移动一个位置，就把当前这个最右边的位置当做老板不发火的最后一天，把这一天用户的评价当做好评，同时看一下第 i - X 天（X天前）的评分，如果哪一天老板发火了，需要把那一天用户的好评分数减去。

时间O(n)

空间O(1)

Java实现

 1 public class Solution {
 2     public int maxSatisfied(int[] customers, int[] grumpy, int x) {
 3         // 前X天happy可以得到的分数
 4         int sum = 0;
 5         for (int i = 0; i < customers.length; i++) {
 6             if (i < x) {
 7                 sum += customers[i];
 8             } else {
 9                 sum += (1 - grumpy[i]) * customers[i];
10             }
11         }
12 
13         int res = sum;
14         for (int i = x; i < customers.length; i++) {
15             // 如果当前生气，但是在窗口内，就可以得分
16             if (grumpy[i] == 1) {
17                 sum += customers[i];
18             }
19             // 如果需要扣分的话，即X天前如果老板生气的话
20             if (grumpy[i - x] == 1) {
21                 sum -= customers[i - x];
22             }
23             res = Math.max(res, sum);
24         }
25         return res;
26     }
27 }

相关题目