1. 题目描述
2. 思路
对于区间问题，很容易先想到前缀和帮助我们优化。
我们可以设，劳累=\(1\)，不劳累=\(-1\)，那么，就是求最大的子区间 [left,right] 使得 s[right]-s[left]-1>0 成立。
其实我们是很容易想到二分的，但在这里，二分有一点小小的问题！
先看一下错误的二分思路：
枚举每个区间长度 len，然后遍历整个区间，查找是否有满足条件的长为 len 的区间。
看起来好像没什么问题吧？其实有个很严重的问题！
我们可以想一下，如果存在长度为 \(x\) 的满足题目要求区间，一定有长度为 \(x-y\)，\(x-y>=0\) 的满足题目要求的区间吗？
这是保证二分正确性的根本要求，即连续性。
其实是不满足的，例如，样例[9,6,9]，它存在长度为 \(3\) 的区间，却不存在长度为 \(2\) 的区间，因此，不具备连续性，也就不能二分。
哎？我们的标题明明是二分啊。
确实，二分其实是可行的！只不过我们要变换一下二分的条件，将“查找是否有满足条件的长为 len 的区间”改为“查找是否有满足条件的长大于等于 len 的区间。”
这样，我们就能保证二分的连续行了！因为如果存在长为 \(x\) 的区间，一定存在长大于等于为 \(x-y\) 的区间，显然成立的！
3. 代码
class Solution {
public:
int longestWPI(vector<int>& hours) {
int n = hours.size();
vector<int> s(n + 10); // 前缀和
vector<int> m(n + 10); // 辅助数组，用来保存最小的左边界
for(int i = 1; i <= n; i ++ ) { // 从 1 开始方便计算
s[i] = s[i - 1] + ((hours[i - 1] > 8) ? 1 : -1);
m[i] = min(m[i - 1], s[i]);
}
function<bool(int)> check = [&](int x) -> bool {
for(int i = x; i <= n; i ++ ) {
// [i-x+1,i]
// 注意，这里是 s[i]-m[i-x]
// 而不是 s[i]-s[i-x]
// 前者找的是“最大”也就是“len>=x”合法区间
// 后者找的是必须满足“len==x”的合法区间
if(s[i] - m[i - x] > 0) return true;
}
return false;
};
int l = 0, r = n;
while(l < r) {
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
};