comments | difficulty | edit_url | rating | source | tags | ||
---|---|---|---|---|---|---|---|
true |
Medium |
1418 |
Weekly Contest 138 Q2 |
|
There is a bookstore owner that has a store open for n
minutes. You are given an integer array customers
of length n
where customers[i]
is the number of the customers that enter the store at the start of the ith
minute and all those customers leave after the end of that minute.
During certain minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i]
is 1
if the bookstore owner is grumpy during the ith
minute, and is 0
otherwise.
When the bookstore owner is grumpy, the customers entering during that minute are not satisfied. Otherwise, they are satisfied.
The bookstore owner knows a secret technique to remain not grumpy for minutes
consecutive minutes, but this technique can only be used 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], minutes = 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.
Example 2:
Input: customers = [1], grumpy = [0], minutes = 1
Output: 1
Constraints:
n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 104
0 <= customers[i] <= 1000
grumpy[i]
is either0
or1
.
According to the problem description, we only need to count the number of customers when the boss is not angry minutes
We define a variable minutes
. Then we traverse the array, each time we move the sliding window, we update the value of
Finally, return
The time complexity is customers
. The space complexity is
class Solution:
def maxSatisfied(
self, customers: List[int], grumpy: List[int], minutes: int
) -> int:
mx = cnt = sum(c * g for c, g in zip(customers[:minutes], grumpy))
for i in range(minutes, len(customers)):
cnt += customers[i] * grumpy[i]
cnt -= customers[i - minutes] * grumpy[i - minutes]
mx = max(mx, cnt)
return sum(c * (g ^ 1) for c, g in zip(customers, grumpy)) + mx
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int cnt = 0;
int tot = 0;
for (int i = 0; i < minutes; ++i) {
cnt += customers[i] * grumpy[i];
tot += customers[i] * (grumpy[i] ^ 1);
}
int mx = cnt;
int n = customers.length;
for (int i = minutes; i < n; ++i) {
cnt += customers[i] * grumpy[i];
cnt -= customers[i - minutes] * grumpy[i - minutes];
mx = Math.max(mx, cnt);
tot += customers[i] * (grumpy[i] ^ 1);
}
return tot + mx;
}
}
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int cnt = 0;
int tot = 0;
for (int i = 0; i < minutes; ++i) {
cnt += customers[i] * grumpy[i];
tot += customers[i] * (grumpy[i] ^ 1);
}
int mx = cnt;
int n = customers.size();
for (int i = minutes; i < n; ++i) {
cnt += customers[i] * grumpy[i];
cnt -= customers[i - minutes] * grumpy[i - minutes];
mx = max(mx, cnt);
tot += customers[i] * (grumpy[i] ^ 1);
}
return tot + mx;
}
};
func maxSatisfied(customers []int, grumpy []int, minutes int) int {
var cnt, tot int
for i, c := range customers[:minutes] {
cnt += c * grumpy[i]
tot += c * (grumpy[i] ^ 1)
}
mx := cnt
for i := minutes; i < len(customers); i++ {
cnt += customers[i] * grumpy[i]
cnt -= customers[i-minutes] * grumpy[i-minutes]
mx = max(mx, cnt)
tot += customers[i] * (grumpy[i] ^ 1)
}
return tot + mx
}
function maxSatisfied(customers: number[], grumpy: number[], minutes: number): number {
let [cnt, tot] = [0, 0];
for (let i = 0; i < minutes; ++i) {
cnt += customers[i] * grumpy[i];
tot += customers[i] * (grumpy[i] ^ 1);
}
let mx = cnt;
for (let i = minutes; i < customers.length; ++i) {
cnt += customers[i] * grumpy[i];
cnt -= customers[i - minutes] * grumpy[i - minutes];
mx = Math.max(mx, cnt);
tot += customers[i] * (grumpy[i] ^ 1);
}
return tot + mx;
}
impl Solution {
pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 {
let mut cnt = 0;
let mut tot = 0;
let minutes = minutes as usize;
for i in 0..minutes {
cnt += customers[i] * grumpy[i];
tot += customers[i] * (1 - grumpy[i]);
}
let mut mx = cnt;
let n = customers.len();
for i in minutes..n {
cnt += customers[i] * grumpy[i];
cnt -= customers[i - minutes] * grumpy[i - minutes];
mx = mx.max(cnt);
tot += customers[i] * (1 - grumpy[i]);
}
tot + mx
}
}