2483. Minimum Penalty for a Shop

題意

• 給一組字串只包含 ’N’ 及 ’Y’

  • Y代表該小時有顧客

  • N代表該小時沒人來

• 字串index即為時間

• 計算商店的 penalty

  • 開店時沒人，penalty增加1

  • 關店時有人，penalty增加1

• 計算最早關店的時間penalty會最小，即可以服務最多人並且空閒時間最少的時間

限制

• 1 <= customers.length <= $10^5$

• customers consists only of characters 'Y' and 'N'.

Test Case

• YYYYYYNNNN ⇒ 有明顯的關門時間

• NNNN ⇒ 沒人，別開了

• YYYY ⇒ 都是人，開到死

• YNYNYNYN ⇒ 1，開到 [1, 3, 5, 7] ，penalty都是1

• NNNNYYYYY ⇒ 9，都不開懲罰為5，開到最後懲罰為4

解題思考

• 簡化問題: str[0..i] 的 N 數量與 str[i + 1..n - 1]的 Y 數量的最小和的位置

• 假設 i=0

  • str[0..i]的 N 數量為0

  • str[i + 1..n - 1]的 Y 數量為字串的全部

• 當每次 i 移動，只要根據 str[i] 對兩端的數量做增減，並不斷記錄最小和及位置便可達到答案

Coding 流程

• 算出 Y 總量 y

  • 開店時間的penalty為 0

  • 關店時間的penalty為 y

• 由 i=0 開始遍歷 customers

  • 當 customer[i] 為 Y，開店時間的penalty不變，關店時間penalty減1

  • 當 customer[i] 為 N，開店時間penalty加1，關店時間penalty不變

  • 若當前penalty總合為最小，紀錄index

Solution

class Solution {
public:
    int bestClosingTime(string customers) {
        const int n = customers.size();
        int open = 0;
        int close = 0;
        for (const char customer : customers) {
            if (customer == 'Y') {
                close += 1;
            }
        }

        int minPenalty = close;
        int index = 0;
        for (int i = 0; i < n; i += 1) {
            if (customers[i] == 'Y') {
                close -= 1;
            } else {
                open += 1;
            }

            if (close + open < minPenalty) {
                minPenalty = close + open;
                index = i + 1;
            }
        }

        return index;
    }
};

Optimization

• 不需要事先計算所有的 Y 數量

• 由於字串兩端的penalty是分開計算的

if (customers[i] == 'Y') {
    close -= 1;
} else {
    open += 1;
}

if (close + open < minPenalty) {}

對penalty的增減都是在 (close + open) 上做的計算

由於不用計算penalty實際數字，只要用一個數字增減，紀錄是否penalty為最小就行了

class Solution {
public:
    int bestClosingTime(string customers) {
        const int n = customers.size();
        int minIndex = 0;
        int count = 0;
        int curr = 0;
        for (int i = 0; i < n; i += 1) {
            if (customers[i] == 'Y') {
                curr -= 1;
            } else {
                curr += 1;
            }

            if (curr < count) {
                count = curr;
                minIndex = i + 1;
            }
        }

        return minIndex;
    }
};