题意：
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1：
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
提示：
1 <= hours.length <= 10000
0 <= hours[i] <= 1
题解：
方法1.（o（n))
贪心，哈希表
大于8的记为1，小于等于1的记为-1；用哈希表维护一些前缀和的位置;从开头遍历数组，如果sum>0，答案更新为i+1,否则在哈希表中查找有没有sum-1的记录，如果有则更新ans=max(ans,i-visit[sum-1])，如果没有sum的记录，则新增 visit[sum]=i;
代码：
class Solution { public: int longestWPI(vector<int>& hours) { int n=hours.size(); int sum=0,ans=0; unordered_map<int,int>visit; for(int i=0;i<n;i++) { sum+=(hours[i]>8?1:-1); if(sum>0) ans=i+1; else { if(visit.find(sum-1)!=visit.end()) ans=max(ans,i-visit[sum-1]); if(visit.find(sum)==visit.end()) visit[sum]=i; } } return ans; } };
方法二：
二分o(nlogn)
前缀和数组sum,sum[0]=0;
对于每一个区间右端点i,我们都期望找到小标最小的0<=j<i，满足sum[j]<sum[i]，作为区间的左端点
如果j>i且sum[j]>sum[i],则j无论如何都不可能成为区间的左端点，因为用i更优
由此可见，我们仅需要维护一个单调递减的数组mono,mono存放下标，对于每一个可能的区间右端点i，通过二分的方法找到最小的j,满足sum[j]<sum[i]
代码：
class Solution { public: int longestWPI(vector<int>& hours) { int n=hours.size(); vector<int>sum(n+1,0); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(hours[i-1]>8?1:-1); int ans=0; vector<int>mono; mono.push_back(0); for(int i=1;i<=n;i++) { int l=0,r=mono.size()-1; while(l<r) { int mid=(l+r)>>1; if(sum[mono[mid]]<sum[i]) r=mid; else l=mid+1; } if(sum[mono[l]]<sum[i]) ans=max(ans,i-mono[l]); else mono.push_back(i); } return ans; } };