162. Moody Shopkeeper
A shopkeeper stays open for n minutes. During minute i, customers[i] people walk in and leave at the end of that minute. When grumpy[i] == 1 the shopkeeper is in a bad mood during that minute and every customer who entered leaves unsatisfied; when grumpy[i] == 0 the customers leave happy.
The shopkeeper knows a breathing trick that keeps the mood calm for exactly minutes consecutive minutes, and it can be used only once. Choose when to use it and return the largest possible number of satisfied customers over the whole day.
Example 1
- Input:
- customers = [2,0,5,1,3]grumpy = [0,1,1,0,1]minutes = 2
- Output:
- 8
- Explanation:
Without the trick, only minutes 0 and 3 are calm, giving 2 + 1 = 3 satisfied. Calming minutes 1 and 2 saves 0 + 5 more, for a total of 8, which beats every other choice.
Example 2
- Input:
- customers = [4,4,4], grumpy = [1,1,1], minutes = 1
- Output:
- 4
- Explanation:
Everyone is unhappy by default. Calming any one minute saves 4 customers, so the answer is 4.
Example 3
- Input:
- customers = [7,2], grumpy = [0,0], minutes = 2
- Output:
- 9
- Explanation:
The shopkeeper is never grumpy, so all 9 customers are satisfied and the trick adds nothing.
Constraints
1 ≤ customers.length ≤ 105
grumpy.length == customers.length
0 ≤ customers[i] ≤ 1000
grumpy[i] is 0 or 1
1 ≤ minutes ≤ customers.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)