LeetCode 1052. 爱生气的书店老板

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

✅ 1052. 爱生气的书店老板

思路分析

解法一：滑动窗口（推荐）

核心思路：

先统计老板不生气时的基础满意人数。

对生气时段使用长度为 X 的滑动窗口，计算可额外挽回的满意人数。

窗口最大值 + 基础满意人数即答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示天数。

空间复杂度：O(1)。

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int base = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                base += customers[i];
            }
        }

        int extra = 0;
        for (int i = 0; i < minutes && i < customers.length; i++) {
            if (grumpy[i] == 1) {
                extra += customers[i];
            }
        }
        int maxExtra = extra;

        for (int i = minutes; i < customers.length; i++) {
            if (grumpy[i] == 1) {
                extra += customers[i];
            }
            if (grumpy[i - minutes] == 1) {
                extra -= customers[i - minutes];
            }
            maxExtra = Math.max(maxExtra, extra);
        }

        return base + maxExtra;
    }
}

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    base := 0
    for i := 0; i < len(customers); i++ {
        if grumpy[i] == 0 {
            base += customers[i]
        }
    }

    extra := 0
    for i := 0; i < minutes && i < len(customers); i++ {
        if grumpy[i] == 1 {
            extra += customers[i]
        }
    }
    maxExtra := extra

    for i := minutes; i < len(customers); i++ {
        if grumpy[i] == 1 {
            extra += customers[i]
        }
        if grumpy[i-minutes] == 1 {
            extra -= customers[i-minutes]
        }
        if extra > maxExtra {
            maxExtra = extra
        }
    }

    return base + maxExtra
}

相似题目

题目	难度	考察点
643. 子数组最大平均数 I	简单	滑动窗口
209. 长度最小的子数组	中等	滑动窗口
995. K 连续位的最小翻转次数	困难	滑动窗口
1248. 统计「优美子数组」	中等	滑动窗口
1052. 爱生气的书店老板	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/83286395