Medium

题目描述

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格大于「不劳累的天数」。

请你返回「表现良好的最长时间段」的长度。

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

示例 2：

输入：hours = [6,6,6]
输出：0

提示：

  • 1 <= hours.length <= 10^4
  • 0 <= hours[i] <= 16

解题思路

这道题可以转换为经典的「寻找最长正数和子数组」问题。

核心思路：

  1. 将原数组转换：工作时间 > 8 的天数记为 +1，否则记为 -1
  2. 问题转化为：寻找和 > 0 的最长子数组
  3. 使用前缀和 + 单调栈优化查找过程

算法步骤：

  1. 计算前缀和数组，其中 prefixSum[i] 表示从开始到位置 i-1 的累计和
  2. 对于每个位置 j，我们要找到最小的 i < j，使得 prefixSum[j] > prefixSum[i]
  3. 使用单调递减栈来维护候选的起始位置，栈中保存可能成为最优起始位置的索引

优化技巧：

  • 当 prefixSum[j] > 0 时，直接返回 j+1（从开始的整个区间）
  • 当 prefixSum[j] <= 0 时，在栈中查找第一个满足 prefixSum[i] < prefixSum[j] 的位置
  • 单调栈保证了查找的高效性，避免了暴力遍历

时间复杂度 O(n)，空间复杂度 O(n)，是此类问题的最优解法。

代码实现

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        vector<int> prefixSum(n + 1, 0);
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + (hours[i] > 8 ? 1 : -1);
        }
        
        int maxLen = 0;
        stack<int> st;
        
        // 构建单调递减栈
        for (int i = 0; i <= n; i++) {
            if (st.empty() || prefixSum[st.top()] > prefixSum[i]) {
                st.push(i);
            }
        }
        
        // 从右往左遍历，查找最长区间
        for (int j = n; j >= 0; j--) {
            while (!st.empty() && prefixSum[st.top()] < prefixSum[j]) {
                maxLen = max(maxLen, j - st.top());
                st.pop();
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        prefix_sum = [0] * (n + 1)
        
        # 计算前缀和
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + (1 if hours[i] > 8 else -1)
        
        max_len = 0
        stack = []
        
        # 构建单调递减栈
        for i in range(n + 1):
            if not stack or prefix_sum[stack[-1]] > prefix_sum[i]:
                stack.append(i)
        
        # 从右往左遍历，查找最长区间
        for j in range(n, -1, -1):
            while stack and prefix_sum[stack[-1]] < prefix_sum[j]:
                max_len = max(max_len, j - stack.pop())
        
        return max_len

public class Solution {
    public int LongestWPI(int[] hours) {
        int n = hours.Length;
        int[] prefixSum = new int[n + 1];
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + (hours[i] > 8 ? 1 : -1);
        }
        
        int maxLen = 0;
        Stack<int> stack = new Stack<int>();
        
        // 构建单调递减栈
        for (int i = 0; i <= n; i++) {
            if (stack.Count == 0 || prefixSum[stack.Peek()] > prefixSum[i]) {
                stack.Push(i);
            }
        }
        
        // 从右往左遍历，查找最长区间
        for (int j = n; j >= 0; j--) {
            while (stack.Count > 0 && prefixSum[stack.Peek()] < prefixSum[j]) {
                maxLen = Math.Max(maxLen, j - stack.Pop());
            }
        }
        
        return maxLen;
    }
}

var longestWPI = function(hours) {
    let maxLen = 0;
    let score = 0;
    let map = new Map();
    
    for (let i = 0; i < hours.length; i++) {
        score += hours[i] > 8 ? 1 : -1;
        
        if (score > 0) {
            maxLen = i + 1;
        } else {
            if (!map.has(score)) {
                map.set(score, i);
            }
            if (map.has(score - 1)) {
                maxLen = Math.max(maxLen, i - map.get(score - 1));
            }
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历数组两次构建栈和查找答案
空间复杂度O(n)前缀和数组和单调栈的空间开销