【数据结构-前缀哈希】力扣1124. 表现良好的最长时间段

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1：
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

示例 2：
输入：hours = [6,6,6]
输出：0

前缀+哈希

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int sum = 0, ans = 0;       
        unordered_map<int, int> group = {{0, -1}};
        for(int i = 0;i < hours.size();i++){
            sum += (hours[i] > 8) ? 1 : -1;

            if(sum > 0){
                ans = i + 1;
            }
            else if(group.find(sum-1) != group.end()){
                ans = max(ans, i - group[sum - 1]);
            }

            if(group.find(sum) == group.end()){
                group[sum] = i;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这一题前缀+哈希并不是空间最优，最优空间是使用贪心+栈的做法，虽然空间复杂度都是O(n)，但是实际的空间使用可能高于 O(n)，因为当哈希表需要扩展时，会预留更多的空间以减少哈希冲突。

sum += (hours[i] > 8) ? 1 : -1;
1

这题的思想就是将大于8小时的天数记+1，小于等于8小时的天数记-1。

 if(sum > 0){
     ans = i + 1;
 }
 else if(group.find(sum-1) != group.end()){
     ans = max(ans, i - group[sum - 1]);
 }
1
2
3
4
5
6

“表现良好的时间段”有两种情况，一种是当前的sum能在哈希表中匹配到sum - 1时（如果是匹配sum的话，这个子段是「劳累的天数」等于「不劳累的天数」。）第二种情况是当sum大于0的时候，这时候说明整个数组都是表现良好的时间段。

if(group.find(sum) == group.end()){
   		group[sum] = i;
}
1
2
3

并且，只哈希表中的键只保存第一次出现的位置。