class Solution {
public:
int longestWPI(vector<int>& hours) {
}
};
1124. 表现良好的最长时间段
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1：
输入：hours = [9,9,6,0,6,6,9] 输出：3 解释：最长的表现良好时间段是 [9,9,6]。
示例 2：
输入：hours = [6,6,6] 输出：0
提示：
1 <= hours.length <= 1040 <= hours[i] <= 16原站题解
java 解法, 执行用时: 15 ms, 内存消耗: 41.9 MB, 提交时间: 2023-02-14 09:40:43
class Solution {
public int longestWPI(int[] hours) {
int ans = 0, s = 0;
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < hours.length; ++i) {
s += hours[i] > 8 ? 1 : -1;
if (s > 0) {
ans = i + 1;
} else if (pos.containsKey(s - 1)) {
ans = Math.max(ans, i - pos.get(s - 1));
}
pos.putIfAbsent(s, i);
}
return ans;
}
}
golang 解法, 执行用时: 24 ms, 内存消耗: 6.3 MB, 提交时间: 2023-02-14 09:40:21
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(x, y int) int { if x < y { return y }; return x }
python3 解法, 执行用时: 64 ms, 内存消耗: 15.7 MB, 提交时间: 2023-02-14 09:33:12
# 前缀和 + 哈希表
class Solution:
def longestWPI(self, hours: List[int]) -> int:
ans = s = 0
pos = {}
for i, x in enumerate(hours):
s += 1 if x > 8 else -1
if s > 0:
ans = i + 1
elif s - 1 in pos:
ans = max(ans, i - pos[s - 1])
if s not in pos:
pos[s] = i
return ans
python3 解法, 执行用时: 84 ms, 内存消耗: 15.9 MB, 提交时间: 2023-02-14 09:29:58
class Solution:
def longestWPI(self, hours: List[int]) -> int:
n = len(hours)
score = [1 if hour > 8 else -1 for hour in hours]
# 前缀和
presum = [0] * (n + 1)
for i in range(1, n + 1):
presum[i] = presum[i - 1] + score[i - 1]
ans = 0
stack = []
# 顺序生成单调栈，栈中元素从第一个元素开始严格单调递减，
# 最后一个元素肯定是数组中的最小元素所在位置
for i in range(n + 1):
if not stack or presum[stack[-1]] > presum[i]:
stack.append(i)
# 倒序扫描数组，求最大长度坡
i = n
while i > ans:
while stack and presum[stack[-1]] < presum[i]:
ans = max(ans, i - stack[-1])
stack.pop()
i -= 1
return ans