Leecode1124表现良好的最长时间段

简介: Leecode1124表现良好的最长时间段

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

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

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

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

示例 1:

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

输出:3

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

提示:

1 <= hours.length <= 10000

0 <= hours[i] <= 16

class Solution {
    public int longestWPI(int[] hours) {
        if(hours == null || hours.length == 0){
            return 0;
        }
        int[] transferArray = new int[hours.length];
        int[] goodDay = new int[hours.length+1];
        goodDay[0]=0;
        int max = 0;
        for(int i=0;i<transferArray.length;++i){
            if(transferArray[i]>8){
                max = 1;
            }
            transferArray[i]=hours[i]>8?1:-1;
            goodDay[i+1]=goodDay[i]+transferArray[i];
        }
        Stack<Integer> stack = new Stack();
        for(int i=0;i<goodDay.length;++i){
            if(stack.isEmpty()){
                stack.push(i);
            }else {
                if(goodDay[i]<goodDay[stack.peek()]){
                    stack.push(i);
                }
            }
        }
        for(int i=goodDay.length-1;i>=0;--i){
            int last = i;
            while(!stack.isEmpty() && goodDay[i]>goodDay[stack.peek()]){
                last = stack.pop();
            }
            if(last != i){
                if(i-last > max){
                    max = i-last;
                }
            }
        }
        return max;
    }
}


相关文章
|
6月前
|
JavaScript 测试技术
【动态规划】【精度】1883. 准时抵达会议现场的最小跳过休息次数
【动态规划】【精度】1883. 准时抵达会议现场的最小跳过休息次数
|
6月前
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
52 0
【动态规划上分复盘】下降路径最小和|礼物的最大价值
【动态规划上分复盘】下降路径最小和|礼物的最大价值
【动态规划刷题 4】礼物的最大价值&&下降路径最小和
【动态规划刷题 4】礼物的最大价值&&下降路径最小和
|
6月前
|
算法
KPM算法求字符串的最小周期证明
公式 `ans = n - LPS[n-1]` 描述了最小周期,其中 `n` 是子串长度,`LPS[n-1]` 是前缀函数值。证明分为特殊情况和一般情况:对于完整周期字符串,`LPS[n-1] = 3*T`,故 `ans = T`;对于非完整周期,通过分析不同长度的 `[末部分]` 和 `[前部分]`,展示 `ans` 始终等于周期 `T` 或由 `[e][b]` 构成的最小周期,从而证明公式正确。
|
6月前
leetcode代码记录(使用最小花费爬楼梯
leetcode代码记录(使用最小花费爬楼梯
35 0
|
6月前
【每日一题Day115】LC2335装满杯子需要的最短总时长 | 贪心
【每日一题Day115】LC2335装满杯子需要的最短总时长 | 贪心
31 0
|
6月前
【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
45 0
|
11月前
|
算法 搜索推荐 Java
算法分析 | 第二套(最差、平均和最佳情况)
算法分析 | 第二套(最差、平均和最佳情况)
41 0
1259:【例9.3】求最长不下降序列 2021-01-15
1259:【例9.3】求最长不下降序列 2021-01-15
120 0