商店的最少代价

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'.

/*
 * Problem Statement:
 * You are given a log of customers visiting a store as a string containing only 'N' and 'Y' characters.
 * 'Y' indicates a customer arrived during that hour, and 'N' indicates no customer arrived.
 * Calculate the minimum cost for closing the store at any hour from 0 to n (inclusive), where
 * closing at hour j means the store is closed during and after the jth hour.
 * Cost is calculated as:
 * 1. For each 'N' during opening hours, the cost increases by 1.
 * 2. For each 'Y' during closing hours, the cost increases by 1.
 * Return the earliest hour j that minimizes the cost.
 */
import java.util.stream.IntStream;

public class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int[] prefixNoCustomers = new int[n + 1];
        int[] suffixCustomers = new int[n + 1];

        // Calculate prefix costs (no customers during open hours)
        IntStream.range(0, n).forEach(i -> prefixNoCustomers[i + 1] = prefixNoCustomers[i] + (customers.charAt(i) == 'N' ? 1 : 0));

        // Calculate suffix costs (customers during closed hours)
        IntStream.range(0, n).map(i -> n - 1 - i).forEach(i -> suffixCustomers[i] = suffixCustomers[i + 1] + (customers.charAt(i) == 'Y' ? 1 : 0));

        // Find the minimum cost and the earliest closing time
        return IntStream.rangeClosed(0, n).reduce((bestTime, j) -> 
            prefixNoCustomers[j] + suffixCustomers[j] < prefixNoCustomers[bestTime] + suffixCustomers[bestTime] ? j : bestTime
        ).orElse(0);
    }
}

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

O(n)

O(1)