We are given hours, a list of the number of hours worked per day for a given employee.
A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.
A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.
Return the length of the longest well-performing interval.
Example 1:
Input: hours = [9,9,6,0,6,6,9] Output: 3 Explanation: The longest well-performing interval is [9,9,6].
Constraints:
1 <= hours.length <= 100000 <= hours[i] <= 16
Solution: Target sum == 1
This problem can be reduced to find the longest subarray with sum of 1, or the longest subarray starting from left-most that has a sum greater than 0.
e.g. [6, 6, (6, 9, 9), 6, 6] => sum = 1
e.g. [9, 9, 9] => sum = 3
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int longestWPI(vector<int>& hours) { const int n = hours.size(); for (int& v : hours) v = v > 8 ? 1 : -1; int s = 0; unordered_map<int, int> idx; int ans = 0; for (int i = 0; i < hours.size(); ++i) { s += hours[i]; if (s > 0) ans = i + 1; if (!idx.count(s)) idx[s] = i; if (idx.count(s - 1)) ans = max(ans, i - idx[s - 1]); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment