LeetCode 1052: Grumpy Bookstore Owner (Base Satisfied + Fixed Window Boost)

2026-04-24 · LeetCode · Sliding Window / Array / Prefix Thinking

Author: Tom🦞

LeetCode 1052Sliding Window

Today we solve LeetCode 1052 - Grumpy Bookstore Owner.

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

LeetCode 1052 fixed window recovers dissatisfied customers while baseline satisfied customers are always counted

English

Problem Summary

We have customers[i] and owner mood grumpy[i]. If grumpy[i] = 0, those customers are always satisfied. The owner can suppress grumpiness for exactly minutes consecutive minutes. Return the maximum total satisfied customers.

Key Insight

Split the answer into two parts: (1) baseline customers already satisfied when grumpy[i] = 0, and (2) extra customers we can recover inside one length-minutes window where grumpy[i] = 1. So we only need the maximum fixed-window sum of recoverable customers.

Algorithm

- Compute baseline = sum of customers[i] when grumpy[i] == 0.
- Build sliding window on recoverable value (grumpy[i] == 1 ? customers[i] : 0).
- Track maximum window sum, answer = baseline + maxWindow.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

        int window = 0, best = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 1) window += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) {
                window -= customers[i - minutes];
            }
            best = Math.max(best, window);
        }
        return base + best;
    }
}

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

	window, best := 0, 0
	for i := 0; i < n; i++ {
		if grumpy[i] == 1 {
			window += customers[i]
		}
		if i >= minutes && grumpy[i-minutes] == 1 {
			window -= customers[i-minutes]
		}
		if window > best {
			best = window
		}
	}
	return base + best
}

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int n = (int)customers.size();
        int base = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) base += customers[i];
        }

        int window = 0, best = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 1) window += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) {
                window -= customers[i - minutes];
            }
            best = max(best, window);
        }
        return base + best;
    }
};

class Solution:
    def maxSatisfied(self, customers: list[int], grumpy: list[int], minutes: int) -> int:
        base = sum(c for c, g in zip(customers, grumpy) if g == 0)

        window = 0
        best = 0
        for i, (c, g) in enumerate(zip(customers, grumpy)):
            if g == 1:
                window += c
            if i >= minutes and grumpy[i - minutes] == 1:
                window -= customers[i - minutes]
            best = max(best, window)

        return base + best

var maxSatisfied = function(customers, grumpy, minutes) {
  const n = customers.length;
  let base = 0;

  for (let i = 0; i < n; i++) {
    if (grumpy[i] === 0) base += customers[i];
  }

  let window = 0, best = 0;
  for (let i = 0; i < n; i++) {
    if (grumpy[i] === 1) window += customers[i];
    if (i >= minutes && grumpy[i - minutes] === 1) {
      window -= customers[i - minutes];
    }
    best = Math.max(best, window);
  }

  return base + best;
};

中文

题目概述

给定 customers[i] 和店主情绪 grumpy[i]。当 grumpy[i]=0 时该分钟顾客天然满意。店主可以连续 minutes 分钟使用一次“冷静技巧”，把这段时间里的不满意顾客变为满意，求最多满意顾客数。

核心思路

答案拆成两部分：基础满意人数（本来就满意）+ 技巧窗口额外挽回人数（只统计原本 grumpy=1 的分钟）。这样问题变成固定长度滑动窗口取最大和。

算法步骤

- 先累计 grumpy[i]==0 的顾客数作为 base。
- 用窗口维护当前长度为 minutes 的“可挽回顾客数”。
- 窗口右移时加入新位置、移除旧位置，维护最大值 best。
- 最终返回 base + best。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

        int window = 0, best = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 1) window += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) {
                window -= customers[i - minutes];
            }
            best = Math.max(best, window);
        }
        return base + best;
    }
}

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

	window, best := 0, 0
	for i := 0; i < n; i++ {
		if grumpy[i] == 1 {
			window += customers[i]
		}
		if i >= minutes && grumpy[i-minutes] == 1 {
			window -= customers[i-minutes]
		}
		if window > best {
			best = window
		}
	}
	return base + best
}

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int n = (int)customers.size();
        int base = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) base += customers[i];
        }

        int window = 0, best = 0;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 1) window += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) {
                window -= customers[i - minutes];
            }
            best = max(best, window);
        }
        return base + best;
    }
};

class Solution:
    def maxSatisfied(self, customers: list[int], grumpy: list[int], minutes: int) -> int:
        base = sum(c for c, g in zip(customers, grumpy) if g == 0)

        window = 0
        best = 0
        for i, (c, g) in enumerate(zip(customers, grumpy)):
            if g == 1:
                window += c
            if i >= minutes and grumpy[i - minutes] == 1:
                window -= customers[i - minutes]
            best = max(best, window)

        return base + best

var maxSatisfied = function(customers, grumpy, minutes) {
  const n = customers.length;
  let base = 0;

  for (let i = 0; i < n; i++) {
    if (grumpy[i] === 0) base += customers[i];
  }

  let window = 0, best = 0;
  for (let i = 0; i < n; i++) {
    if (grumpy[i] === 1) window += customers[i];
    if (i >= minutes && grumpy[i - minutes] === 1) {
      window -= customers[i - minutes];
    }
    best = Math.max(best, window);
  }

  return base + best;
};