Medium

题目描述

给你一个用字符串 customers 表示的商店客户访问日志，该字符串由字符 ‘N’ 和 ‘Y’ 组成：

  • 如果第 i 个字符是 ‘Y’，表示第 i 小时有客户到来
  • 如果第 i 个字符是 ‘N’，表示第 i 小时没有客户到来

如果商店在第 j 小时关门（0 <= j <= n），罚金按以下方式计算：

  • 商店营业期间每小时没有客户到来，罚金增加 1
  • 商店关门期间每小时有客户到来，罚金增加 1

返回商店必须关门以获得最小罚金的最早小时。

注意：如果商店在第 j 小时关门，意味着商店在第 j 小时是关闭的。

示例 1：

输入: customers = "YYNY"
输出: 2
解释: 
- 第 0 小时关门的罚金为 1+1+0+1 = 3
- 第 1 小时关门的罚金为 0+1+0+1 = 2
- 第 2 小时关门的罚金为 0+0+0+1 = 1
- 第 3 小时关门的罚金为 0+0+1+1 = 2
- 第 4 小时关门的罚金为 0+0+1+0 = 1
第 2 或第 4 小时关门都能获得最小罚金。由于 2 更早，最优关门时间是 2。

示例 2：

输入: customers = "NNNNN"
输出: 0
解释: 最好在第 0 小时关门，因为没有客户到来。

示例 3：

输入: customers = "YYYY"
输出: 4
解释: 最好在第 4 小时关门，因为每小时都有客户到来。

约束条件：

  • 1 <= customers.length <= 10^5
  • customers 仅由字符 ‘Y’ 和 ‘N’ 组成

解题思路

解题思路

这是一道典型的前缀和问题。对于每个可能的关门时间 j，罚金由两部分组成：

  1. 开门期间没有客户的小时数（前 j 小时中 ‘N’ 的个数）
  2. 关门期间有客户来的小时数（后面小时中 ‘Y’ 的个数）

方法一：直接模拟（时间复杂度较高）

遍历所有可能的关门时间，分别计算每种情况下的罚金，找出最小值。

方法二：前缀和优化（推荐）

关键观察：在时刻 j 关门的罚金 = 前 j 小时的 ‘N’ 个数 + 后面小时的 ‘Y’ 个数。

我们可以预先计算：

  • 前缀 ‘N’ 的个数：prefixN[j] 表示前 j 小时 ‘N’ 的个数
  • 后缀 ‘Y’ 的个数：suffixY[j] 表示从第 j 小时开始的 ‘Y’ 个数

方法三：一次遍历优化（最优）

更进一步，我们发现当关门时间从 j 移动到 j+1 时：

  • 如果 customers[j] 是 ‘N’，罚金减少 1（少了一个开门无客户的惩罚）
  • 如果 customers[j] 是 ‘Y’，罚金增加 1（多了一个关门有客户的惩罚）

因此可以通过一次遍历，动态维护罚金变化，找到最小值。

代码实现

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.length();
        int penalty = 0;
        
        // 计算初始罚金（在第0小时关门）
        for (char c : customers) {
            if (c == 'Y') penalty++;
        }
        
        int minPenalty = penalty;
        int bestTime = 0;
        
        // 遍历所有关门时间
        for (int j = 0; j < n; j++) {
            // 从第j小时关门变为第j+1小时关门
            if (customers[j] == 'Y') {
                penalty--; // 减少一个关门期间有客户的罚金
            } else {
                penalty++; // 增加一个开门期间无客户的罚金
            }
            
            if (penalty < minPenalty) {
                minPenalty = penalty;
                bestTime = j + 1;
            }
        }
        
        return bestTime;
    }
};

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)
        
        # 计算初始罚金（在第0小时关门）
        penalty = customers.count('Y')
        min_penalty = penalty
        best_time = 0
        
        # 遍历所有关门时间
        for j in range(n):
            # 从第j小时关门变为第j+1小时关门
            if customers[j] == 'Y':
                penalty -= 1  # 减少一个关门期间有客户的罚金
            else:
                penalty += 1  # 增加一个开门期间无客户的罚金
            
            if penalty < min_penalty:
                min_penalty = penalty
                best_time = j + 1
        
        return best_time

public class Solution {
    public int BestClosingTime(string customers) {
        int n = customers.Length;
        int penalty = 0;
        
        // 计算初始罚金（在第0小时关门）
        foreach (char c in customers) {
            if (c == 'Y') penalty++;
        }
        
        int minPenalty = penalty;
        int bestTime = 0;
        
        // 遍历所有关门时间
        for (int j = 0; j < n; j++) {
            // 从第j小时关门变为第j+1小时关门
            if (customers[j] == 'Y') {
                penalty--; // 减少一个关门期间有客户的罚金
            } else {
                penalty++; // 增加一个开门期间无客户的罚金
            }
            
            if (penalty < minPenalty) {
                minPenalty = penalty;
                bestTime = j + 1;
            }
        }
        
        return bestTime;
    }
}

var bestClosingTime = function(customers) {
    let n = customers.length;
    let minPenalty = Infinity;
    let bestHour = 0;
    
    for (let j = 0; j <= n; j++) {
        let penalty = 0;
        
        for (let i = 0; i < j; i++) {
            if (customers[i] === 'N') {
                penalty++;
            }
        }
        
        for (let i = j; i < n; i++) {
            if (customers[i] === 'Y') {
                penalty++;
            }
        }
        
        if (penalty < minPenalty) {
            minPenalty = penalty;
            bestHour = j;
        }
    }
    
    return bestHour;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串长度，只需要遍历一次字符串
空间复杂度O(1)，只使用了常数额外空间

相关题目