Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1052.html
1052. Grumpy Bookstore Owner (Medium)
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
Related Topics:
Array, Sliding Window
Solution 1. Sliding Window
// OJ: https://leetcode.com/problems/grumpy-bookstore-owner/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int ans = 0, sum = 0;
for (int i = 0; i < customers.size(); ++i) sum += grumpy[i] == 0 ? customers[i] : 0;
for (int i = 0; i < customers.size(); ++i) {
if (grumpy[i] == 1) sum += customers[i];
if (i >= X && grumpy[i - X] == 1) sum -= customers[i - X];
if (i >= X - 1) ans = max(ans, sum);
}
return ans;
}
};
-
class Solution { public int maxSatisfied(int[] customers, int[] grumpy, int X) { int satisfied = 0; int length = customers.length; for (int i = 0; i < length; i++) { if (grumpy[i] == 0) satisfied += customers[i]; } int unsatisfiedWindow = 0; for (int i = 0; i < X; i++) { if (grumpy[i] == 1) unsatisfiedWindow += customers[i]; } int maxUnsatisfiedWindow = unsatisfiedWindow; for (int i = X; i < length; i++) { int prevIndex = i - X; if (grumpy[prevIndex] == 1) unsatisfiedWindow -= customers[prevIndex]; if (grumpy[i] == 1) unsatisfiedWindow += customers[i]; maxUnsatisfiedWindow = Math.max(maxUnsatisfiedWindow, unsatisfiedWindow); } return satisfied + maxUnsatisfiedWindow; } } ############ class Solution { public int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int s = 0, cs = 0; int n = customers.length; for (int i = 0; i < n; ++i) { s += customers[i] * grumpy[i]; cs += customers[i]; } int t = 0, ans = 0; for (int i = 0; i < n; ++i) { t += customers[i] * grumpy[i]; int j = i - minutes + 1; if (j >= 0) { ans = Math.max(ans, cs - (s - t)); t -= customers[j] * grumpy[j]; } } return ans; } }
-
// OJ: https://leetcode.com/problems/grumpy-bookstore-owner/ // Time: O(N) // Space: O(1) class Solution { public: int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) { int ans = 0, sum = 0; for (int i = 0; i < customers.size(); ++i) sum += grumpy[i] == 0 ? customers[i] : 0; for (int i = 0; i < customers.size(); ++i) { if (grumpy[i] == 1) sum += customers[i]; if (i >= X && grumpy[i - X] == 1) sum -= customers[i - X]; if (i >= X - 1) ans = max(ans, sum); } return ans; } };
-
class Solution: def maxSatisfied( self, customers: List[int], grumpy: List[int], minutes: int ) -> int: s = sum(a * b for a, b in zip(customers, grumpy)) cs = sum(customers) t = ans = 0 for i, (a, b) in enumerate(zip(customers, grumpy), 1): t += a * b if (j := i - minutes) >= 0: ans = max(ans, cs - (s - t)) t -= customers[j] * grumpy[j] return ans ############ # 1052. Grumpy Bookstore Owner # https://leetcode.com/problems/grumpy-bookstore-owner/ class Solution: def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int: n = len(customers) A = [i for i in range(n) if grumpy[i] == 1] res = customers[A[0]] if A else 0 if A: curr, start = customers[A[0]], 0 for index in A[1:]: if index - A[start] < minutes: curr += customers[index] else: while index - A[start] >= minutes: curr -= customers[A[start]] start += 1 curr += customers[index] res = max(res, curr) return res + sum(customers[i] for i in range(n) if grumpy[i] == 0)
-
func maxSatisfied(customers []int, grumpy []int, minutes int) int { s, cs := 0, 0 for i, c := range customers { s += c * grumpy[i] cs += c } t, ans := 0, 0 for i, c := range customers { t += c * grumpy[i] j := i - minutes + 1 if j >= 0 { ans = max(ans, cs-(s-t)) t -= customers[j] * grumpy[j] } } return ans } func max(a, b int) int { if a > b { return a } return b }
-
impl Solution { pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 { let k = minutes as usize; let n = customers.len(); let mut sum = 0; for i in 0..k { if grumpy[i] == 1 { sum += customers[i]; } } let mut max = sum; for i in k..n { if grumpy[i - k] == 1 { sum -= customers[i - k]; } if grumpy[i] == 1 { sum += customers[i]; } max = max.max(sum); } sum = 0; for i in 0..n { if grumpy[i] == 0 { sum += customers[i]; } } sum + max } }