3 min read leetcode

2483. Minimum Penalty for a Shop

2483. Minimum Penalty for a Shop
Photo by Markus Spiske / Unsplash

題意

  • 給一組字串只包含 'N' 及 'Y'
    • Y 代表該小時有顧客
    • N 代表該小時沒人來
  • 字串的 index 即為時間
  • 計算商店的 penalty
    • 開店時沒人，penalty 增加 1
    • 關店時有人，penalty 增加 1
  • 計算最早關店的時間，使得 penalty 會最小，也就是可以服務最多人並且空閒時間最少的時間

限制

  • 1 <= customers.length <= 10^5
  • customers 只包含 'Y' 和 '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 數量為整個字串的 Y 數
  • 當每次 i 移動，只要根據 str[i] 對兩端的數量做增減，並不斷記錄最小和及位置，就能得到答案

Coding 流程

  • 算出 Y 總量 y
    • 開店時間的 penalty 為 0
    • 關店時間的 penalty 為 y
  • 由 i=0 開始走訪 customers
    • 當 customers[i] 為 Y，開店時間的 penalty 不變，關店時間 penalty 減 1
    • 當 customers[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) 上做加減運算
只要記錄 (close + open) 是否為最小即可，不需要額外計算 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;
    }
};

時間與空間複雜度

不論是第一段程式或第二段程式，皆只需要走訪整個字串一次，每個索引執行常數時間的判斷與加減運算，因此 時間複雜度 為 O(n)。
同時，我們僅使用若干變數（如 open, close, curr, count 等）來記錄當前狀態，並未佔用額外與輸入長度正比的空間，故 空間複雜度 為 O(1)。

Justin