商店的最少代价

标签: 字符串 前缀和

难度: Medium

给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：

  • 如果第 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 <= 105
  • customers 只包含字符 'Y' 和 'N' 。

Submission

运行时间: 68 ms

内存: 17.0 MB

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        ans = 0
        cost = 0
        for i, c in enumerate(customers,1):
            if c == 'N': 
                cost += 1
            else:
                cost -= 1
                if cost < 0:
                    ans = i 
                    cost = 0
        return ans

Explain

题解的思路是遍历一次字符串customers，使用一个cost变量来跟踪开门期间没有顾客('N')和关门期间有顾客到达('Y')的代价。每次遇到'N'，代价加1；遇到'Y'，代价减1。如果cost变为负值，这意味着到目前为止如果一直开门，将没有额外代价。因此，将ans更新为当前小时数，并将cost重置为0。最终返回的ans是最早的时间点，使得之后关门的代价最小。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        ans = 0  # 用于记录最早的最佳关闭时间
        cost = 0  # 用于记录到当前时间为止的总代价
        for i, c in enumerate(customers, 1):  # 从1开始遍历customers
            if c == 'N':
                cost += 1  # 如果当前小时没有顾客，代价加1
            else:
                cost -= 1  # 如果当前小时有顾客，代价减1
                if cost < 0:  # 如果代价变为负值，更新最佳关闭时间
                    ans = i  # 更新最佳关闭时间为当前时间
                    cost = 0  # 重置代价为0
        return ans  # 返回最早的最佳关闭时间

Explore

这种处理方式的合理性在于代价(cost)代表了保持门开的总成本。当'N'出现时，即没有顾客到访，若门是开的则产生了不必要的成本，因此代价增加1。相反，当'Y'出现时，表示有顾客到访，如果此时门是开的，这是必要的，因此相对于关门状态来说，开门是节省了成本，故代价减少1。这种计算方式反映了保持门开状态的经济效益或损失。

当cost变成负值时，这意味着从开始到当前时间点开门的总代价是负的，即开门比关门更省成本，因此这个时间点之前开门是合算的。更新ans为当前时间点，是因为这可能是关门成本最小化的最佳时间。重置cost为0是为了重新计算从这个时间点开始到后面的代价，以便找到可能存在的下一个更优的关门时间。

从索引1开始遍历customers字符串是为了使每个索引直接对应于小时数，便于理解和实现。这样处理使得在更新最佳关闭时间ans时直接使用索引值，无需额外的转换或调整，从而简化了代码实现。对最终结果的影响是确保ans精确地反映了小时数，而不是数组的下标。

是的，应该处理customers为空字符串的情况。在当前代码实现中，如果customers为空字符串，则不进入循环，直接返回ans的初始值0。但在实际应用中，这可能不是期望的行为，因为没有顾客数据时可能更合适的返回值是一个表示无效或不适用的特殊值，例如-1或null，来明确表示没有合适的关闭时间。