网站建设开场白,上海建网站计划,手机网站图片 触摸 放大代码 js,可以自己制作动画的appLeetCode-1124. 表现良好的最长时间段【哈希表#xff0c;前缀和#xff0c;单调栈】题目描述#xff1a;解题思路一#xff1a;查字典。cur是当前的前缀和(劳累与不劳累天数之差)#xff0c;向前遍历。有两种情况。情况一#xff0c;若cur大于0则是[0,i]的劳累与不劳累天…
LeetCode-1124. 表现良好的最长时间段【哈希表前缀和单调栈】题目描述解题思路一查字典。cur是当前的前缀和(劳累与不劳累天数之差)向前遍历。有两种情况。情况一若cur大于0则是[0,i]的劳累与不劳累天数之差一定最大记录下答案。情况二若cur小于等于0用哈希表记录cur(只记录对应最小的)。去哈希表里找到cur-1对应的下标j那么[j,i]的前缀和为cur-(cur-1)10记录下答案。解题思路二单调栈。将大于8的当做1小于等于8的当做-1(劳累与不劳累天数之差)即是s[i]-s[j]。要找大的s[i]小的s[j]解题思路三0题目描述
给你一份工作时间表 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 https://leetcode.cn/problems/longest-well-performing-interval/description/
解题思路一查字典。cur是当前的前缀和(劳累与不劳累天数之差)向前遍历。有两种情况。情况一若cur大于0则是[0,i]的劳累与不劳累天数之差一定最大记录下答案。情况二若cur小于等于0用哈希表记录cur(只记录对应最小的)。去哈希表里找到cur-1对应的下标j那么[j,i]的前缀和为cur-(cur-1)10记录下答案。
class Solution {
public:int longestWPI(vectorint hours) {unordered_mapint,int index;int cur0,ans0,nhours.size();for(int i0;in;i){if(hours[i]8) cur;else --cur;if(cur0) ansi1;//cur是[0,i]的劳累与不劳累天数之差一定最大。else{//cur小于等于0的情况if(index.count(cur-1)0) ansmax(ans,i-index[cur-1]);//找到cur-1的下标j,则j到i的和是cur-(cur-1)10,cur大于0就判断一下。if(!index.count(cur)) index[cur]i;//只记录一次即是前缀和对应下标最小的}}return ans;}
};时间复杂度O(n) 空间复杂度O(n)
解题思路二单调栈。将大于8的当做1小于等于8的当做-1(劳累与不劳累天数之差)即是s[i]-s[j]。要找大的s[i]小的s[j]
class Solution {
public:int longestWPI(vectorint hours) {int nhours.size(),ans0,s[n1];//前缀和stackint st;st.push(s[0]0);for(int j1;jn;j){s[j]s[j-1](hours[j-1]8?1:-1);//初始化前缀和if(s[j]s[st.top()]) st.push(j);//感兴趣的j必然是递减的}for (int in;i;--i)while(!st.empty()s[i]s[st.top()]){ansmax(ans,i-st.top());//[栈顶,i)可能是最长子数组st.pop();}//i之前有可能前缀和更大return ans;}
};时间复杂度O(n) 空间复杂度O(n)
解题思路三0
