1052. An angry bookstore owner

This is the 30th day of my participation in the August Text Challenge.More challenges in August

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.

Tip:

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

Their thinking

To maintain a sliding window of size X, we need to find a window period that increases the maximum number of satisfied customers (i.e. find the window with the maximum number of dissatisfied customers).

code

class Solution {
   public int maxSatisfied(int[] customers, int[] grumpy, int X) {


        int l=0,r=0,n=customers.length,sum=0,res=0,c=0,rl=0,rr=0;
        while (r<n)// Count only the sliding window of unsatisfied customers
        {
            if(grumpy[r]==1)
            sum+=customers[r];
            if(r-l+1>X)
            {
                if(grumpy[l]==1)
                sum-=customers[l];
                l++;
            }
            if(sum>=res) { res=sum; rl=l; rr=r;// Record the window location and the number of unsatisfied customers
            }
            r++;
        }
        for (int i = 0; i < n; i++) {

            if (grumpy[i]==0)
                c+=customers[i];
            else if(i>=rl&&i<=rr)   c+=customers[i];// All customers in the results window become satisfied
        }
        returnres+c; }}Copy the code

Time complexity: O(n), where N is the length of customers and Grumpy arrays. You need to traverse both arrays twice each.

Space complexity: O(1).

1052. An angry bookstore owner