Question

Formatted question description: https://leetcode.ca/all/1124.html


Algorithm

Code

Java

  • 
    
    
  • // OJ: https://leetcode.com/problems/longest-well-performing-interval/
    // Time: O(NlogN)
    // Space: O(N)
    class Solution {
    public:
        int longestWPI(vector<int>& A) {
            int N = A.size(), ans = 0;
            for (int &n : A) n = n > 8 ? 1 : -1;
            vector<int> prefix(N + 1), s{0};
            for (int i = 0; i < N; ++i) prefix[i + 1] = prefix[i] + A[i];
            for (int i = 1; i <= N; ++i) {
                if (prefix[i] == prefix[s.back()]) continue;
                else if (prefix[i] < prefix[s.back()]) s.push_back(i);
                else {
                    auto it = upper_bound(begin(s), end(s), prefix[i], [&](int a, int b) { return prefix[b] < a; });
                    ans = max(ans, i - *it);
                }
            }
            return ans;
        }
    };
    
  • # 1124. Longest Well-Performing Interval
    # https://leetcode.com/problems/longest-well-performing-interval/
    
    class Solution:
        def longestWPI(self, hours: List[int]) -> int:
            n = len(hours)
            seen = {}
            res = v = 0
            
            for i, h in enumerate(hours):
                v = v + 1 if h > 8 else v - 1
                            
                if v > 0:
                    res = i + 1
                    
                seen.setdefault(v, i)
    
                if v - 1 in seen:
                    res = max(res, i - seen[v - 1])
            
            return res
    
    

All Problems

All Solutions