1124. Longest Well-Performing Interval

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a  tiring day  if and only if the number of hours worked is (strictly) greater than 8.

well-performing interval  is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Constraints:

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

这道题说是有一个每天工作的时长数组,若每天工作时间超过8个小时,则表示是劳累的一天。又定义了一个所谓的表现良好的区间(从资本家的角度来定义的吧?!!),即劳累的天数大于不劳累的天数,然后让返回表现良好的区间的最大长度。亮点在于给的例子,上来就是传说中的 996,而且最终返回的表现良好的区间正好是这个 996,非常具有讽刺意味,估计是出题者有意为之。这道题跟之前那道 Contiguous Array 的解法很类似,都是玩子数组的题。虽然博主之前说过子数组求极值的题十有八九都是用动态规划来做,但是这道题正好是一个例外。由于这里我们只关心数组中的数字是否大于8,而不关心其具体的大小,所以可以进行转换,将大于8的数字均变为1,小于等于8的变为 -1,这样变换的好处是,只要个子数组之和大于0了,则说明一定是一个表现良好的区间。这里用一个变量 cur,表示从开头到当前位置的子数组之和,在遍历数组的过程中,若大于8,则 cur 加上1,否则减去1。若此时 cur 大于0,则说明从开头到当前位置的子数组是一个良好区间,直接将结果 res 更新为 i+1。若 cur 为非正数,说明从开头到当前位置不是一个良好区间,但中间可能还有较小的良好区间。需要用一个 HashMap 来建立子数组之和跟其结束位置坐标之间的映射,由于子数组之和可能重复,所以我们只建立最先出现的,后面再次出现则不更新,这样保证了其坐标最小。所以对于当前的非正数 cur,只有当其不存在映射的时候,才建立映射。此时再找一下,看 cur-1 是否存在,由于 cur-1 的映射值(若存在的话)一定是小于 cur 的,这样二者做差,中间那段区间一定是良好区间,因为其和为1,这样就可以用这个长度来更新结果 res 了,参见代码如下:

解法一:

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int res = 0, n = hours.size(), cur = 0;
        unordered_map<int, int> seen;
        for (int i = 0; i < n; ++i) {
            cur += hours[i] > 8 ? 1 : -1;
            if (cur > 0) {
                res = i + 1;
            } else {
                if (!seen.count(cur)) {
                    seen[cur] = i;
                }
                if (seen.count(cur - 1)) {
                    res = max(res, i - seen[cur - 1]);
                }
            }
        }
        return res;
    }
};

这道题的提示说是让用单调栈来做,也不是不可以,但感觉没有上面的那种解法来的更加直接。这里是要建立原数组的累加和数组,注意还是要用到之前的小技巧,将大于8的数字变为1,否则变为 -1。然后遍历一遍累加和数组,若栈为空,或者栈顶元素大于当前数字,则将当前数字压入栈,注意这里我们压入的是坐标,而不是真正的数组元素。由于累加和数字的首元素是0,而之后又只压入更小的数字,则后面的负数均被压入栈了。然后从末尾开始遍历,只要当前的值大于栈顶元素,说明二者中间的区域是一个良好区间,通过坐标来求出区间长度并更新结果 res,这个核心原理跟上面的一样,更新后将元素出栈,继续跟下一个较大的栈顶元素对比,若还是当前的大,则继续计算区间长度并更新 res,直到当前元素小了,则继续往前用下一个比较,或者是当栈为空了,则停止,参见代码如下:

解法二:

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int res = 0, n = hours.size();
        stack<int> st;
        vector<int> sums(n + 1);
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
        }
        for (int i = 0; i <= n; ++i) {
            if (st.empty() || sums[st.top()] > sums[i]) {
                st.push(i);
            }
        }
        for (int i = n; i >= 0; --i) {
            while (!st.empty() && sums[st.top()] < sums[i]) {
                res = max(res, i - st.top());
                st.pop();
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1124

类似题目:

Contiguous Array

参考资料:

https://leetcode.com/problems/longest-well-performing-interval/

https://leetcode.com/problems/longest-well-performing-interval/discuss/334565/JavaC%2B%2BPython-O(N)-Solution-Life-needs-996-and-669

https://leetcode.com/problems/longest-well-performing-interval/discuss/335163/O(N)-Without-Hashmap.-Generalized-ProblemandSolution%3A-Find-Longest-Subarray-With-Sum-greater-K.

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation