526互联

[LeetCode] 2483. Minimum Penalty for a Shop

发布时间 2023-08-30 02:45:19作者: CNoodle

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 }

 

LeetCode 题目总结