2483. Minimum Penalty for a Shop - Medium

前往題目

想法

• sliding windows?
• 要看有幾個n幾個y

思路

實際上就是算出每個位置的prefix_n和postfix_y，因為沒有客人來沒有關店會penalty，相反的，有客人卻已經關店也要penalty

1. 紀錄prefix_n，但不用包含當前
2. 紀錄postfix_y，要包含當前
3. 然後再疊代每個位置，把prefix和postfix加起來找出最小值，並回傳其index

Code

class Solution {
    public int bestClosingTime(String customers) {
        int len = customers.length();
        int[] prefix_n = new int[len + 1];
        int[] postfix_y = new int[len + 1];
        
        // Fill in 0
        prefix_n[0] = 0;
        postfix_y[len] = 0;

        //Count prefix n
        for (int i = 1; i < len + 1; ++i) {
            prefix_n[i] = prefix_n[i - 1];

            // Closed at the moment is fine, but closed 1 hr later will cause penalty
            if (customers.charAt(i - 1) == 'N') {
                prefix_n[i]++;
            }
        }

        // Count postfix y
        for (int i = len - 1; i >= 0; --i) {
            postfix_y[i] = postfix_y[i + 1];

            if (customers.charAt(i) == 'Y') {
                postfix_y[i]++;
            }
        }

        int minPen = Integer.MAX_VALUE;
        int res = 0;

        for (int i = 0; i < len + 1; ++i) {
            int pen = prefix_n[i] + postfix_y[i];

            if (pen < minPen) {
                res = i;
                minPen = pen;
            }
        }

        return res;
    }
}