08-30 leetcode-2483

题目：

You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters ‘N’ and ‘Y’:

if the ith character is ‘Y’, it means that customers come at the ith hour
whereas ‘N’ indicates that no customers come at the ith hour.
If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as follows:

For every hour when the shop is open and no customers come, the penalty increases by 1.
For every hour when the shop is closed and customers come, the penalty increases by 1.
Return the earliest hour at which the shop must be closed to incur a minimum penalty.

Note that if a shop closes at the jth hour, it means the shop is closed at the hour j.

这题的题意比较好理解，核心在于罚款规则

开着没客户罚款
关着有客户罚款

题解

首先最直觉的做法是前缀和

一个时刻的罚款可以通过这样的等式算出

假设当前关店，我们求出前面有多少时刻没有客户，以及关店后有多少时刻有客户就 OK 了

最直觉的写法

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        length, count_n, count_y = 0, 0, 0
        n_prefix, y_prefix = [0], [0]
        for item in customers:
            count_n += 1 if item == "N" else 0
            n_prefix.append(count_n)
        for item in customers[::-1]:
            count_y += 1 if item == "Y" else 0
            y_prefix.append(count_y)
        result, _ = min(
            enumerate(a + b for a, b in zip(n_prefix, y_prefix[::-1])),
            key=lambda x: x[1],
        )
        return result

但是这个做法实际上是 O(n+logn) 的，而且额外的数组空间也比较恶心，那么有没有更简便的写法？

有

那么我们做这样几个假设

假设数组中第 i 个位置时前面 N 的个数为 count[i]
那么我们可以求出位置 i 左侧 Y 的个数为 i-count[i]，我们假设传入的数据内有 K 个 Y，那么右侧的 Y 的个数为 k-i+count[i]
那么我们总的代价公式为 k + cnt[i] + cnt[i] - i
由于 k 是个常数，那么我们只需要在遍历时记录更新 cnt[i] + cnt[i] - i 即可

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        counter_n = 0
        result, min_score = 0, 0
        for index, item in enumerate(customers):
            if item == "N":
                counter_n += 1
            if counter_n + counter_n - (index + 1) < min_score:
                result, min_score = index + 1, counter_n + counter_n - (index + 1)
        return result

这下时间复杂度 O(N)，空间 O(1) 了

Comment