problem:1124. 表现良好的最长时间段

思路：把题意转换一下>8的数为1,<=8的数为-1，这样就是求和大于0的最长子区间，又利用前缀和的性质$o(1)$时间求某个区间的和，[a,b]区间和为s[b]-s[a-1]>0则s[b]>s[a-1]所以转换为求i<j,s[i]<s[j]问题。这样就变成了母题

Accode:

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        vector<int> sums;
        sums.push_back(0);
        for(auto i:hours){
            if(i>8) sums.push_back(sums.back()+1);
            else sums.push_back(sums.back()-1);
        }
        stack<int> sta;
        for(int i=0;i<sums.size();i++){
            while(sta.size()==0 || sums[sta.top()]>sums[i]){
                sta.push(i);
            }
        }
        int ans = 0;
        for(int j=sums.size()-1;j>=0;j--){
            while(sta.size() && sums[sta.top()]<sums[j]){
                ans = max(ans,j-sta.top());
                sta.pop();
            }
        }
        return ans;
    }
};

时间复杂度$o(n)$