1052.Grumpy-Bookstore-Owner

1052. Grumpy Bookstore Owner

题目地址

https://leetcode.com/problems/grumpy-bookstore-owner/

题目描述

Today, the bookstore owner has a store open for customers.length minutes.  Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy.  If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0.  When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

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

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

代码

Approach #1 Sliding Window

class Solution {
  public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        // 1. 计算原本就开心的客户数量 n base
    int baseCount = 0;
    for (int i = 0; i < customers.length; i++) {
      if (grumpy[i] == 0) {
        baseCount += customers[i];
      }
    }

    // 2. 生成 不开心客户的数组
    int[] sadCustomers = new int[customers.length];
    for (int i = 0; i < customers.length; i++) {
      if (grumpy[i] == 1) {
        sadCustomers[i] = customers[i];
      }
    }

    // 3. 计算 X 分钟板蓝根 所带来的最大收益
    // 3.1 先计算 前 X 分钟的收益
    int gain = 0;
    for (int i = 0; i < X; i++) {
      gain += sadCustomers[i];
    }

    // 3.2 采用 改变量 计算接下来每个区间的 收益并 记录最大值
    int maxGain = gain;
    for (int i = X; i < sadCustomers.length; i++) {
      gain += sadCustomers[i];
      gain -= sadCustomers[i - X];
      if (gain > maxGain) {
        maxGain = gain;
      }
    }

    // 4. 求和
    return baseCount + maxGain;
  }
}

Approach #2

class Solution {
  public int maxSatisfied(int[] customers, int[] grumpy, int X) {
    int maxGrumpy = 0;
    int happy = 0;
    int g = 0;
    for (int i = 0; i < customers.length; i++) {
      if (i >= X) {
        g = g - (customers[i - X] * grumpy[i - X]);
      }
      g += (customers[i] * grumpy[i]);
      maxGrumpy = Math.max(maxGrumpy, g);
      if (grumpy[i] == 0) {
        happy += customers[i];
      }
    }

    happy += maxGrumpy;
    return happy;
  }
}