力扣1124.表现良好的最长时间段
-
哈希表存最小的下标
- 当s[i] > 0 那么他到头可以构成一个合法时间段
- 否则 找到之前的 s[i] - 1 的下标:
- 因为连续的前缀和一定只相差1
- 若想算更小的s[i] - 2,s[i] - 3…
- 一定会先算到s[i] - 1
- 那么这些更小数必然在 s[i]−1 首次出现的位置的右边
-
class Solution { public: int longestWPI(vector<int>& hours) { int n = hours.size(); vector<int> s(n+1); for(int i=0;i<n;i++) { s[i+1] = s[i]; s[i+1] += hours[i] > 8 ? 1 : -1; cout<<s[i+1]<<endl; } unordered_map<int,int> cnt; int res=0; for(int i=0;i<=n;i++) { if(s[i] > 0) res = max(res,i); if(cnt.find(s[i] - 1) != cnt.end()) res = max(res,i - cnt[s[i] - 1]); if(cnt.find(s[i]) == cnt.end()) cnt[s[i]] = i; } return res; } };