LeetCode 1124. 表现良好的最长时间段（单调栈/哈希）

1. 题目

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

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

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

请你返回「表现良好时间段」的最大长度（好剥削啊，一定要劳累才行）。

示例 1：
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
 
提示：
1 <= hours.length <= 10000
0 <= hours[i] <= 16

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-well-performing-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 类似题目：LeetCode 962. 最大宽度坡（单调栈）

2.1 单调栈

class Solution {
   
public:
    int longestWPI(vector<int>& hours) {
   
    	int n = hours.size(), i = 0;
    	vector<int> sum(n+1, 0);
    	for(i = 1; i <= n; i++)
    	{
   
    		sum[i] = (hours[i-1]>8 ? 1 : -1) + sum[i - 1];//记录前缀和，第一个是0
    	}
    	stack<int> s;
    	int maxlen = 0;
    	for(i = 0; i < n+1; i++)
    	{
   
    		if(s.empty() || sum[s.top()] > sum[i])//单调递减栈
    		    s.push(i);
    	}
        for(i = n; i >= 0 && !s.empty(); i--)
        {
   
            while(!s.empty() && sum[i] > sum[s.top()])
            {
   
                maxlen = max(maxlen, i-s.top());
                s.pop();
            }
        }
    	return maxlen;
    }
};

52 ms 21.6 MB

2.2 哈希

class Solution {
   
public:
    int longestWPI(vector<int>& hours) {
   
    	int n = hours.size(), maxlen = 0, sum=0;
    	unordered_map<int, int> m;
    	for(int i = 0; i < n; ++i)
    	{
   
            sum += hours[i]>8 ? 1 : -1;
            if(sum > 0)//和大于0，全部满足条件
                maxlen = i+1;
            else
            {
   
                if(m.count(sum-1))//第一次出现的前一种状态（sum-1）存在吗
                    maxlen = max(maxlen, i-m[sum-1]);
                if(!m.count(sum))//存下第一次出现的当前状态
                    m[sum] = i;
            }
    	}
    	return maxlen;
    }
};

68 ms 21.9 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载：https://blog.csdn.net/qq_21201267/article/details/108536922