[LeetCode] 2483. Minimum Penalty for a Shop

CNoodle / 2023-08-30 / 原文

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.

Example 1:

Input: customers = "YYNY"
Output: 2
Explanation: 
- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.

Example 2:

Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0th hour as no customers arrive.

Example 3:

Input: customers = "YYYY"
Output: 4
Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.

Constraints:

1 <= customers.length <= 105
customers consists only of characters 'Y' and 'N'.

商店的最少代价。

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

如果第 i 个字符是 'Y' ，它表示第 i 小时有顾客到达。

如果第 i 个字符是 'N' ，它表示第 i 小时没有顾客到达。

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

在开门期间，如果某一个小时没有顾客到达，代价增加 1 。

在关门期间，如果某一个小时有顾客到达，代价增加 1 。

请你返回在确保代价最小的前提下，商店的最早关门时间。

注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。

我一开始的思路是扫描两遍，第一遍从左往右扫描，统计 input 字符串里有多少个 Y，记为 total；第二遍从右往左扫描，在每个 index 上，如果当前这个位置是 Y，那么我的 cost 就加一，意思是如果我在当前这个位置关门，我的代价是多少，最后我看一下全局到底在哪个位置关门，付出的代价最小。后来我发觉这个思路是错的。这个思路是来源是例子一，如果你在某个位置上关了门，在这个位置右边的所有 N 是没有代价的。

正确的思路是前缀和，从左往右扫描一遍，遇到 Y 就加一，意思是如果我在当前这个位置不关门，我的收益是多少；遇到 N 就减一，因为如果在当前位置不关门且没有顾客到达，我是要付出代价的。如此遍历整个 input 字符串，找到收益最大的下标，如果有多个收益最大的下标，取最小的那个。

如果只想扫描一遍，就一定要试着把前缀和的定义想清楚，把代价如何计算放进去。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int bestClosingTime(String customers) {
 3         int n = customers.length();
 4         int sum = 0;
 5         int res = 0;
 6         int p = -1;
 7         for (int i = 0; i < n; i++) {
 8             sum += customers.charAt(i) == 'Y' ? 1 : -1;
 9             if (sum > res) {
10                 res = Math.max(res, sum);
11                 p = i;
12             }
13         }
14         return p + 1;
15     }
16 }