1124.表现良好的最长时段
同类题目
题目描述
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。请你返回「表现良好时间段」的最大长度。
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
解题思路
题意剖析：题目意思是对于hours 中的每个元素，大于8记为1，否则记为-1，要我们算标记后的数组中，和大于0的最长区间。
解法1：暴力
两重for 循环，但是无法AC。第一重循环用于计算从下标 0,到当前下标 i的前缀和第二重循环用于计算从下标 0，到当前下标 j 的前缀和，两者前缀和的差值若均大于0，则符合条件，此时需要通过判断对返回值 ret 进行更新。
解法2：哈希
用一个 cur 变量记录前缀和，当大于8时，cur++, 小于8时，cur–。由于从前向后遍历，当 cur > 0时，说明从开始到现在满足条件，时间必然是最长的，直接更新 res = i + 1。当 cur <= 0时呢？关键来了
这里用一个 字典记录所有 cur <= 0的最小下标，所谓最小，就是后面如果再碰到了同样的 cur，不需要更新，如果没有碰到过，则把这个下标记录下来。然后用 cur - 1 去字典里找，如果找到了下标j，那么就说明从0到 j 的前缀和是 cur-1，而从0到 i 的前缀和是 cur，那么显然从 j 到 i的和是（cur - (cur - 1)） = 1 > 0，也就是说从 j+1到 i 的表现肯定是满足的，并且由于 j 是 cur-1中最小的，所以 i-j 是最大的。此时再跟 res 比较看是否需要更新。
上面为什么只需要查找 cur-1？因为满足条件的前缀和只能是小于等于cur-1的，也就是说其实也可以查找 cur-2,cur-3…，但是，cur-2的下标一定不可能在 cur-1的下标左边。使用反证法，前提是cur-1代表的是最小下标，那么如果 cur-2在 cur-1左边，而cur-2的左边一定还会有 cur-1出现（cur值是从0开始的），这就和最小下标的前提矛盾了。
那么问题又来了，如果 cur-1不存在，是否要查找 cur-2,cur-3…呢？也不需要，思路跟上面是一样的，如果 cur-1不存在，cur-2,cur-3…一定也不存在。举个例子，不可能从0跳到-2，-3，而中间没有-1。
通过上面有理有据的分析，下面的代码就很简单了。
解法3：单调栈
其思路和哈希方法一致，但由于没有哈希表的开销，因此运行速度大大加快。
代码
//暴力：超时
class Solution {
public:
int longestWPI(vector<int>& hours) {
int ret=0;
int sum=0;
for(int i=0;i<hours.size();i++){
sum+=hours[i]>8?1:(-1);
int tmpSum=0;
for(int j=0;j<=i;j++){
if(sum-tmpSum>0){
ret=max(ret,i-j+1);
}
tmpSum+=hours[j]>8?1:(-1);
}
}
return ret;
}
};//哈希表
class Solution {
public:
int longestWPI(vector<int>& hours) {
int ret=0;
unordered_map<int,int> mymap;
int cur=0;
for(int i=0;i<hours.size();i++){
if(hours[i]>8) cur++;
else cur--;
if(cur>0) ret=i+1;
else{
if(mymap.count(cur-1)) ret=max(ret,i-mymap[cur-1]);
if(mymap.count(cur)==0) mymap[cur]=i;
}
}
return ret;
}
};// 单调栈(单调减)
class Solution {
public:
int longestWPI(vector<int>& hours) {
int ret=0;
vector<int> sum(hours.size()+1,0);
stack<int> minStack;
minStack.push(0);
for(int i=0;i<hours.size();i++){
sum[i+1]=hours[i]>8?sum[i]+1:sum[i]-1;
if(sum[minStack.top()]>sum[i+1]) minStack.push(i+1);
}
for(int i=sum.size()-1;i>=0;i--){
while(minStack.size() && sum[i]-sum[minStack.top()]>0){
ret=max(ret,i-minStack.top());
minStack.pop();
}
}
return ret;
}
};