1124.表现良好的最长时间段-526互联

问题描述

给你一份工作时间表 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先出现在前缀和数组中。

代码

单调栈

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;
    }
};

哈希表

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;
    }
};