Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1124.html
Algorithm
Code
-
-
// 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; } };
-
class Solution: def longestWPI(self, hours: List[int]) -> int: ans = s = 0 seen = {} for i, h in enumerate(hours): s += 1 if h > 8 else -1 if s > 0: ans = i + 1 else: if s not in seen: seen[s] = i if s - 1 in seen: ans = max(ans, i - seen[s - 1]) 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
-
func longestWPI(hours []int) (ans int) { s := 0 pos := map[int]int{} for i, x := range hours { if x > 8 { s++ } else { s-- } if s > 0 { ans = i + 1 } else if j, ok := pos[s-1]; ok { ans = max(ans, i-j) } if _, ok := pos[s]; !ok { pos[s] = i } } return } func max(a, b int) int { if a > b { return a } return b }