[leetcode每日一题]2.14

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

难度中等253

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

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

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

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

示例 1：

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

示例 2：

输入：hours = [6,6,6]
输出：0

提示：

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

Solution

前缀和两维遍历。勉强能过。

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        int prefix[10005] = {0};
        for(int i=0;i<n;i++){
            prefix[i+1] += prefix[i] + (hours[i] > 8 ? 1 : -1);
        }
        int res = 0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(prefix[j] < prefix[i]){
                    res = max(res, i - j);
                    break;
                }
            }
        }
        return res;
    }
};

优化：可以使用哈希表记录每一个数据第一次出现的下标。

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/longest-well-performing-interval/solution/biao-xian-liang-hao-de-zui-chang-shi-jia-rlij/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

优化2：可以使用栈。

正序遍历，每次入栈的元素都要比当前栈顶元素小。这样确保了每一次的访问都是下标第一小的元素，即区间左端点最小。

之后倒序遍历前缀和数组，用当前元素匹配栈顶元素。如果当前元素比栈顶元素大，那么就合法，弹出栈顶并更新当前答案，直到栈顶元素比当前元素小，则前缀和数组遍历下一个元素。这样能够保证区间右端点最大。

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        vector<int> s(n + 1);
        stack<int> stk;
        stk.push(0);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
            if (s[stk.top()] > s[i]) {
                stk.push(i);
            }
        }

        int res = 0;
        for (int r = n; r >= 1; r--) {
            while (stk.size() && s[stk.top()] < s[r]) {
                res = max(res, r - stk.top());
                stk.pop();
            }
        }
        return res;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/longest-well-performing-interval/solution/biao-xian-liang-hao-de-zui-chang-shi-jia-rlij/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

很巧妙地一道题。不过充满了资本家的恶趣味。