1124 表现良好的最长时间段.md

题目描述

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

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

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

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

示例 1：

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

输出：3

解释：最长的表现良好时间段是 [9,9,6]。

提示：

• 1 <= hours.length <= 10000
• 0 <= hours[i] <= 16

思路分析

建立前缀和数组，代表当前之前所有工作时长 > 8h的天数，则两个元素的差 > 0 表示表现良好的时间段，求最长的部分。

1. 双重循环。对每个i都向后查找。
2. 单调栈。发现转换为求 i<j && nums[i]<nums[j] 的最大跨度问题，和962求最大坡度一样的操作。
   • 从左往右，建立单调递减栈，保存出现的最小值的下标。
   • 从右往左，查找元素大于栈顶，更新最大跨度。

代码实现

    public int longestWPI(int[] hours) {
        int[] preSum = new int[hours.length + 1];
        int max = 0;
        for (int i = 0; i < hours.length; i++) {
            preSum[i + 1] = hours[i] > 8 ? preSum[i] + 1 : preSum[i] - 1;
        }
        //双重循环超时
        /*for (int i = 0; i < preSum.length - 1; i++) {
            for (int j = i + 1; j < preSum.length; j++) {
                if (preSum[j] - preSum[i] > 0) {
                    max = Math.max(max, j - i);
                }
            }
        }*/

        //单调栈
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < preSum.length; i++) {
            if (preSum[i] < preSum[stack.peek()]) {
                stack.push(i);
            }
        }

        for (int i = preSum.length - 1; i >= 0; i--) {
            while (stack.size() != 0 && preSum[i] > preSum[stack.peek()]) {
                max = Math.max(max, i - stack.pop());
            }
        }
        return max;
    }