# 1124.表现良好的最长时间段

## 问题描述
[1124. 表现良好的最长时间段 (Medium)](https://leetcode.cn/problems/longest-well-performing-interval/)

给你一份工作时间表 `hours`，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 `8` 小时的时候，那么这一天就是「 **劳累的一天**」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 **大于**「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
**示例 1：**
```
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
```
**示例 2：**
```
输入：hours = [6,6,6]
输出：0
```
**提示：**
- `1 <= hours.length <= 10⁴`
- `0 <= hours[i] <= 16`

## 解题思路
### 单调栈
首先，将原数组中大于8的值设为1，小于或等于8的值设为-1，分别表示劳累的一天和不劳累的一天，然后求这个新数组的前缀和，得到一个前缀和数组`prefix`；

那么我们就是要求满足`prefix[j] > prefix[i]`条件下的最大的`j - i`，首先，我们考虑左端点，如果`prefix[i1] < prefix[i2]`且`i1 <= i2`，那么我们完全不需要考虑使用`i2`作为左端点，因为选择`i1`作为左端点的`res`一定更大，所以我们可以正向遍历`prefix`，并将索引`idx`压入单调栈，满足栈底到栈顶单调递减；

然后，我们从**从右往左**遍历`prefix`找右端点，如果`prefix[j1] > prefix[stk.top()]`，那就弹出栈顶元素并更新`res = std::max(res, r - stk.top())`，如果选择从左往右遍历的话，`prefix[j2] < prefix[stk.top()]`的时候，最终结果可能是`j2 - i`，其中`i`是一个被弹出的元素，从左往右遍历右端点，这种情况无法考虑到。

### 哈希表
- 如果`prefix[i] > 0`，说明这`i`天内都是表现良好的时间段，那么`res = max(i, res)`；
- 如果`prefix[i] <= 0`，如果`key` `prefix[i]`之前未在哈希表`ump`中出现过，那么`ump[prefix[i]] = i`, 否则不更新`ump[prefix[i]]`，因为哈希表中`key`对应的`value`一定更小，对应的差值即时间长度会更大， 以第`i`天结尾表现良好的时间段的最大长度即为`ump[prefix[i]] - ump[prefix[i] - 1]`（要求`key` `prefix[i] - 1`在哈希表中，否则为0，即不存在这样的时间段），这是因为由于新数组中只有1和-1两种元素，那么值`prefix[i] - 1`一定比`prefix[i] - 2`先出现在前缀和数组中。

## 代码
### 单调栈
```cpp
class Solution {
  public:
    int longestWPI(vector<int> &hours) {
        int n = hours.size();
        if (n == 1) {
            return hours[0] > 8;
        }
        for (auto &i : hours) {
            if (i > 8) {
                i = 1;
            } else {
                i = -1;
            }
        }
        // 计算新hours的前缀和
        vector<int> prefix(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + hours[i - 1];
        }
        //
        stack<int> l_stk;
        int res = 0;
        l_stk.push(0);
        for (int i = 1; i <= n; i++) {
            if (prefix[i] > 0) {
                res = std::max(res, i);
            }
            if (prefix[i] < prefix[l_stk.top()]) {
                l_stk.push(i);
            }
        }
        for (int r = n; r >= 1; r--) {
            while (!l_stk.empty() && prefix[r] > prefix[l_stk.top()]) {
                if (l_stk.empty()) {
                    return std::max(r, res);
                }
                res = std::max(res, r - l_stk.top());
                l_stk.pop();
            }
        }
        return res;
    }
};
```

### 哈希表
```cpp
class Solution {
  public:
    int max(int a, int b) {
        return a > b ? a : b;
    }
    int longestWPI(vector<int> &hours) {
        int n = hours.size();
        // 大于8的转化为1，小于等于8的转化为-1
        for (auto &i : hours) {
            if (i > 8) {
                i = 1;
            } else {
                i = -1;
            }
        }
        // 计算新hours的前缀和
        vector<int> prefix(n, 0);
        prefix[0] = hours[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + hours[i];
        }
        unordered_map<int, int> mp; // 前缀相同时，保留下标最小的那个
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (prefix[i] > 0)
                res = max(res, i + 1);
            else {
                auto iter = mp.find(prefix[i] - 1);
                if (iter != mp.end()) {
                    res = max(res, i - iter->second);
                }
                if (mp.find(prefix[i]) == mp.end()) {
                    mp[prefix[i]] = i;
                }
            }
        }
        return res;
    }
};
```