LeetCode 1124. 表现良好的最长时间段（单调栈/哈希）

示例 1：
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。
 
提示：
1 <= hours.length <= 10000
0 <= hours[i] <= 16

class Solution {
public:
    int longestWPI(vector<int>& hours) {
    	int n = hours.size(), i = 0;
    	vector<int> sum(n+1, 0);
    	for(i = 1; i <= n; i++)
    	{
    		sum[i] = (hours[i-1]>8 ? 1 : -1) + sum[i - 1];//记录前缀和，第一个是0
    	}
    	stack<int> s;
    	int maxlen = 0;
    	for(i = 0; i < n+1; i++)
    	{
    		if(s.empty() || sum[s.top()] > sum[i])//单调递减栈
    		    s.push(i);
    	}
        for(i = n; i >= 0 && !s.empty(); i--)
        {
            while(!s.empty() && sum[i] > sum[s.top()])
            {
                maxlen = max(maxlen, i-s.top());
                s.pop();
            }
        }
    	return maxlen;
    }
};

class Solution {
public:
    int longestWPI(vector<int>& hours) {
    	int n = hours.size(), maxlen = 0, sum=0;
    	unordered_map<int, int> m;
    	for(int i = 0; i < n; ++i)
    	{
            sum += hours[i]>8 ? 1 : -1;
            if(sum > 0)//和大于0，全部满足条件
                maxlen = i+1;
            else
            {
                if(m.count(sum-1))//第一次出现的前一种状态（sum-1）存在吗
                    maxlen = max(maxlen, i-m[sum-1]);
                if(!m.count(sum))//存下第一次出现的当前状态
                    m[sum] = i;
            }
    	}
    	return maxlen;
    }
};