This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1052 on LeetCode. Angry Bookstore owner, medium difficulty.

Tag: “sliding window”, “double pointer”

Today, the bookshop owner has a shop ready for a trial opening. Customers [I] enter the store every minute, and all of them leave at the end of that minute.

At some point, bookstore owners get angry. If the bookstore owner is grumpy at the ith minute, then grumpy = 1, otherwise grumpy = 0. When the bookstore owner is angry, customers are dissatisfied for a minute. When they are not, they are satisfied.

Bookshop owners know a secret technique that can suppress their emotions and keep them from getting angry for X minutes, but they can only use it once.

Please return this day to business down, up to how many customers can be satisfied with the number.

Example:

Customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1, 1,0,1,0,1], X = 3 Maximum number of satisfied customers = 1 + 1 + 1 + 7 + 5 = 16.Copy the code

Tip:

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

The sliding window

Since the “technique” only changes the mood from “angry” to “not angry,” not angry is still not angry.

  1. We can first add satisfied customers into the answer and change the corresponding customers[I] to 0.

  2. The next problem is: find a contiguous subarray of length x in Customers, maximizing the sum. This is the part of the customer that we use the technique to get.

class Solution {
    public int maxSatisfied(int[] cs, int[] grumpy, int x) {
        int n = cs.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                ans += cs[i];
                cs[i] = 0; }}int max = 0, cur = 0;
        for (int i = 0, j = 0; i < n; i++) {
            cur += cs[i];
            if (i - j + 1 > x) cur -= cs[j++];
            max = Math.max(max, cur);
        }
        returnans + max; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1052 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.