1124

Posted on In , Views:

題目:
https://leetcode.com/problems/longest-well-performing-interval/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        map<int, int> mp; // prefixSum, firstIndex
        mp[0] = -1;
        int ans = 0;
        int sum = 0;
        for(int i=0; i<hours.size(); ++i){
            sum += hours[i] > 8 ? 1 : -1; // hours[i] > 8, sum++; hours[i] <= 8, sum--;
            if(sum > 0) ans = i + 1;
            else if(mp.count(sum-1)) ans = max(ans, i - mp[sum-1]);
            if(!mp.count(sum)) mp[sum] = i;
        }
        return ans;
    }
};