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

题目描述

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

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

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

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

示例 1：

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

提示：

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

思路

准备工作
将$工作时间>8小时$记为1，$<8$记为$-1$，计算前缀和presum。

暴力枚举

  • 使用两根指针，i，j去枚举区间(j,i)，记录最大的i-j，可以进行适度剪枝，but仍旧超时。
  • 时间复杂度：$O(n^2)$，空间复杂度：$O(n)$
  • c++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        int res = 0;
        vector<int> presum(n + 1);
        for(int i = 0;i < n;++i) {
            presum[i + 1] = presum[i] + (hours[i] > 8? 1 : -1 );
        }
        for(int i = n;i > 0;--i) {
            for(int j = 0;j < i;++j) {
                if(i - j <= res) break;
                if(presum[i] - presum[j] > 0) {
                    res = max(res, i - j);
                }
            }
        }
        return res;
    }
};
二分查找（错误）
  • 枚举区间值，l = 0，r = n
前缀和+单调栈+双指针

转化之后的问题与962. 最大宽度坡类似，使用单调栈。

双指针也不一定要有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        vector<int> presum(n + 1);
        for(int i = 0;i < n;++i) {
            presum[i + 1] = presum[i] + (hours[i] > 8?1:-1);
        }
        stack<int> s;
        int res = 0;
        for(int i = 0;i <= n;++i) {
            if(s.empty() || presum[s.top()] > presum[i]) {
                s.push(i);
            }
        }
        int i = n;
        while(i >= 0 && !s.empty()) {
            while(!s.empty() && presum[i] > presum[s.top()]) {
                res = max(res, i - s.top());
                s.pop();
            }
            --i;
        }
        return res;
    }
};