题目描述

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

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

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

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

样例

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

限制

• 1 <= hours.length <= 10000
• 0 <= hours[i] <= 16

算法1

(二分) $O(n \log n)$

1. 我们将大于 8 的数字看做 1，小于等于 8 的数字看做 -1。
2. 先求出前缀和数组 sum，下标从 1 开始且 sum[0] = 0。
3. 对于每个可能的区间右端点 i ，我们都期望找到下标最小的 0 <= j < i，满足 sum[j] < sum[i]，作为作为区间的左端点。
4. 我们发现，如果 i' > i 且 sum[i'] > sum[i]，则 i' 无论如何都不会成为 2 中备选的左端点，因为总可以用 i 来替代使得答案更优。
5. 由此可见，我们仅需要维护一个单调递减的数组 mono，mono 中存放下标，对于每个可能的区间右端点 i，通过二分的方式在 mono 中找到最小的 j，满足 sum[j] < sum[i]。
6. 注意，mono 初始时需要放入 0 下标。

时间复杂度

• 共有 $n$ 个右端点，每次二分的时间复杂度为 $O(\log n)$，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 前缀和数组， mono 数组都需要占用 $O(n)$ 的空间。

C++ 代码

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        vector<int> sum(n + 1, 0);

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

        int ans = 0;
        vector<int> mono;
        mono.push_back(0);

        for (int i = 1; i <= n; i++) {
            int l = 0, r = mono.size() - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (sum[mono[mid]] < sum[i])
                    r = mid;
                else
                    l = mid + 1;
            }
            if (sum[mono[l]] < sum[i])
                ans = max(ans, i - mono[l]);

            if (sum[i] < sum[mono[mono.size() - 1]])
                mono.push_back(i);
        }

        return ans;
    }
};

算法2

(贪心，哈希表) $O(n)$

1. 我们将大于 8 的数字看做 1，小于等于 8 的数字看做 -1。
2. 我们用一个变量维护当前的前缀和 sum，并维护一个哈希表 visited 记录某些前缀和的位置。
3. 从开头遍历数组，如果 sum > 0，则显然答案直接更新为 i + 1。
4. 否则，我们在哈希表中查看是不是有 sum - 1 的 key，如果有，则更新 ans = max(ans, i - visited[sum - 1])；然后如果哈希表中没有 sum 的 key，则新增 visited[sum] = i。
5. 为什么我们只需要找 sum - 1 就可以了呢？这是因为任何一个小于 0 的前缀和，如果能找到满足条件的左端点，其最优的左端点一定是值等于 sum - 1 且下标 最小 的那个位置。其正确性很容易证明，任何一个小于 0 的前缀和，如果能找到满足条件的左端点，前缀和必定都是经过若干次降低升高，然后到当前的 sum 的，而且升高降低的过程一定是连续的，所以 第一次 降低到 sum - 1 的位置是最优的（不可能有第一次升高到 sum - 1 的位置）。

时间复杂度

• 每个位置遍历一次，哈希表单次操作的时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 哈希表需要额外 $O(n)$ 的空间。

C++ 代码

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        int sum = 0, ans = 0;

        unordered_map<int, int> visited;
        for (int i = 0; i < n; i++) {
            sum += (hours[i] > 8 ? 1 : -1);
            if (sum > 0)
                ans = i + 1;
            else {
                if (visited.find(sum - 1) != visited.end())
                    ans = max(ans, i - visited[sum - 1]);
                if (visited.find(sum) == visited.end())
                    visited[sum] = i;
            }
        }

        return ans;
    }
};