专门做布料的网站,五星酒店网站建设方案,网络营销的发展趋势和前景,旅游电子商务网站建设试题文章目录1. 题目2. 解题2.1 单调栈2.2 哈希1. 题目
给你一份工作时间表 hours#xff0c;上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候#xff0c;那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」#xff0c;意…
文章目录1. 题目2. 解题2.1 单调栈2.2 哈希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(vectorint hours) {int n hours.size(), i 0;vectorint sum(n1, 0);for(i 1; i n; i){sum[i] (hours[i-1]8 ? 1 : -1) sum[i - 1];//记录前缀和第一个是0}stackint s;int maxlen 0;for(i 0; i n1; 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(vectorint hours) {int n hours.size(), maxlen 0, sum0;unordered_mapint, int m;for(int i 0; i n; i){sum hours[i]8 ? 1 : -1;if(sum 0)//和大于0全部满足条件maxlen i1;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阿明一起加油、一起学习进步
