题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个一维数组，其中的每一个值代表一个时间段有没有客人到来（Y 有，N 无），现在需要选择能使代价最小的关门时间，关门前一个时间段无客人就 1 代价，关门后一个时间段有人就有 1 代价。

思路分享

  • 这边第一时间实现的方法，是先求了 Y 和 N 的前缀和，结合各自的总和，对整个日志做依次遍历，过程中结合上面的值 O（1）计算代价。虽然过了，但消耗的时间和空间所有人中属于较多的。

  • 但是灵神提出了能显著降低消耗的时间与空间的方法。前缀和不需要提前求，遍历过程中直接实时计算，遍历的当前点，也就是假设开始时所有点都在关门后，让当前时间为关门时间，左边遇到一个 Y 就让代价 -1，否则 +1，这样子就迅速地得到了所有所有的代价，自然也就能获取其中的最小值。

    https://leetcode.cn/problems/minimum-penalty-for-a-shop/solutions/1993077/qian-hou-zhui-fen-jie-o1-kong-jian-by-en-c2m5/?envType=daily-question&envId=2025-12-26

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def bestClosingTime(self, customers: str) -> int:
        # 灵神的解法
        ans = penalty = min_penalty = 0
        for i, c in enumerate(customers):
            penalty += 1 if c == "N" else -1
            if penalty < min_penalty:
                ans = i+1
                min_penalty = penalty
        return ans
        # 最初的解法
        n = len(customers)
        y_acc = [0]
        n_acc = [0]
        for i, c in enumerate(customers):
            y_acc.append(y_acc[i]+(1 if c == "Y" else 0))
            n_acc.append(n_acc[i]+(1 if c == "N" else 0))
        y_sum = customers.count("Y")
        n_sum = customers.count("N")
        ans = 0
        min_val = inf
        for i in range(n+1):
            cur_val = n_acc[i] + y_sum - y_acc[i]
            if cur_val < min_val:
                min_val = cur_val
                ans = i 
        return ans