Leetcode 2483 - Minimum Penalty for a Shop

題目

Problem#

給你一個由 Y 和 N 組成的字串 customers 其中第 $i$ 個字元 customers[i] 代表第 $i$ 個小時有沒有客人來
令 $j$ 等於關店的時間，有兩條規則：

• 如果店開著的時候沒有客人來的話，扣一點
• 如果有客人在店關了之後來的話，扣一點

問你能不能回傳最早的小時，其扣點最大？

測資限制#

• $1 \le n \le 10^5$: 字串長度，只包含 Y, N

想法#

• 暴力：枚舉 $j=[0, n-1]$ 關店的時間，跟著規則統計 $O(n^2)$ -> TLE

• 用前綴和可以在 $O(1)$ 查詢得知區間的 Y 或 N 的數量，需花費 $O(n)$ 構建陣列

• 時間複雜度: $\mathcal{O}(n)$

• 空間複雜度: $\mathcal{O}(n)$

AC Code#

Copy

class Solution {
public:
    int bestClosingTime(string c)
    {
        int siz = c.size();
        vector<int> y(siz), n(siz);
 
        for(int i = 0; i < siz; i++)
        {
            bool ok = c[i] == 'N';
            n[i] = i == 0 ? ok : n[i-1] + ok;
        }
 
        for(int i = siz-1; i >= 0; i--)
        {
            bool ok = c[i] == 'Y';
            y[i] = i == siz-1 ? ok : y[i+1] + ok;
        }
 
        int ans = INT_MAX;
        int ansH = 0;
        for(int i = 0; i < siz+1; i++)
        {
            int tmp = 0;
            tmp += i < siz ? y[i] : 0;
            tmp += i > 0 ? n[i-1] : 0;
            if(tmp < ans)
            {
                ans = tmp;
                ansH = i;
            }
        }
 
        return ansH;
    }
};

view raw leetcode/2483.cpp delivered with ❤ by emgithub