[LeetCode] 1124. Longest Well-Performing Interval

[grandyang]

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.

A  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 同步地址:

#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 题目讲解汇总(持续更新中...)