1124. 表現良好的最長時間段

哈希表

將工作大於八小時的那幾天轉換為 $-1$ ，小於等於八小時的天轉換為 $1$ ，題目就是要求子數組的總和要大於零。
只需要在每次加入之前檢查哈希表內小於自己的數值有多少，就知道有幾個數值可以列入參考，
這個方法速度很慢，時間複雜度 $O(n^2)$ ，建議用第二種方法

程式碼

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        unordered_map<int, int> umap;
        int sum = 0, res = 0;
        umap[0] = -1;
        for(int i = 0; i < hours.size(); i++) {
            if(hours[i] > 8) { // 勞累
                sum++;
            }
            else { // 不勞累
                sum--;
            }
            for(auto [prev_sum, pos] : umap) {
                if(sum > prev_sum) { // sum - prev_sum > 0, 代表這段時間內整體為正, 勞累
                    res = max(res, i - pos);
                }
            }
            if(!umap.contains(sum)) {
                umap[sum] = i;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(n)$

優化

我們將數組的所有元素轉換為了 $1,-1$，而滿足條件的數組總和要大於 $0$。

• 如果當前總和 sum > 0，可以直接列入參考答案。
• 如果當前總和 sum <= 0，只要找到前面是否出現過 sum - 1，取得所在的位置 pos，將 i - pos 列入參考答案。

比如現在的 sum = -3，就去找有沒有出現過 sum = -4，其他能配對的 -5，-6 都不需要考慮。
因為要想有 -5 出現，就必然在那之前出現 -4。 既然 -4 出現的會比較早，那跟 -4 配對就是最佳選擇。

程式碼

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        unordered_map<int, int> umap;
        int sum = 0, res = 0;
        for(int i = 0; i < hours.size(); i++) {
            sum += hours[i] > 8 ? 1 : -1;
            if(sum > 0) {
                res = i + 1; // res - (-1)
            }
            else if(umap.contains(sum - 1)) 
                res = max(res, i - umap[sum - 1]);
            }
            if(!umap.contains(sum)) { // 第一次出現的數字
                umap[sum] = i;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$