雨中黄叶树
灯下白头人
单调栈的题总是让我很难理解，虽然看到这道题时眼前一亮（无产者团结起来！！！）。。。
这道题首先需要进行转化，转成[1, -1]数组，比如：
A: 9 9 6 0 6 6 9
B: 1 1 -1 -1 -1 -1 1
问题转化成：找到数组B中，连续且整数和大于0的最长序列。
如果求下标i到j的连续和，要么用之间连续的数相加，要么用[0, j]的和减去[0, i-1]的和。
所以可以转化前缀和数组：
B: 1 1 -1 -1 -1 -1 1
C: 0 1 2 1 0 -1 0 1
于是题意就变成了，找和数组C中在满足C[j] - C[i] > 0的情况下，j - i + 1的最大值。
单调栈最常用解决什么问题？
满足某个条件时的最长的连续子序列
所以还是看代码吧，要睡觉了：
class Solution {
public:
int longestWPI(vector<int>& hours) {
for (int &it : hours)
it = it > 8 ? 1 : -1;
int presum = 0;
for (int &it : hours) {
int temp = it;
it = presum;
presum += temp;
}
hours.push_back(presum);
vector<int> s;
s.reserve(hours.size());
int ans = 0;
for (int i = 0; i < hours.size(); i++) {
if (s.empty() || hours[s.back()] >= hours[i])
s.emplace_back(i);
}
for (int i = hours.size() - 1; i >= 0; i--) {
while(!s.empty() && hours[s.back()] < hours[i]) {
ans = max(ans, i - s.back());
s.pop_back();
}
}
return ans;
}
};
