LeetCode-1124. 表现良好的最长时间段【哈希表，前缀和，单调栈】

题目描述：

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

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= hours.length <= 10⁴
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)=1>0，记录下答案。

class Solution {
public:int longestWPI(vector<int>& hours) {unordered_map<int,int> index;int cur=0,ans=0,n=hours.size();for(int i=0;i<n;++i){if(hours[i]>8) ++cur;else --cur;if(cur>0) ans=i+1;//cur是[0,i]的劳累与不劳累天数之差，一定最大。else{//cur小于等于0的情况if(index.count(cur-1)>0) ans=max(ans,i-index[cur-1]);//找到cur-1的下标j,则j到i的和是cur-(cur-1)=1>0,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(vector<int> &hours) {int n=hours.size(),ans=0,s[n+1];//前缀和stack<int> st;st.push(s[0]=0);for(int j=1;j<=n;++j){s[j]=s[j-1]+(hours[j-1]>8?1:-1);//初始化前缀和if(s[j]<s[st.top()]) st.push(j);//感兴趣的j，必然是递减的}for (int i=n;i;--i)while(!st.empty()&&s[i]>s[st.top()]){ans=max(ans,i-st.top());//[栈顶,i)可能是最长子数组st.pop();}//i之前有可能前缀和更大return ans;}
};

时间复杂度：O(n)
空间复杂度：O(n)

解题思路三：0