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 <= 104
• 0 <= hours[i] <= 16

思路

这个是leetcode在情人节给出的一个恶趣味，以996作为开端。

解题思路

针对这道题，一开始的思路便是模拟，根据题目的内容，计算的是一个子区间的长度， 由于输入的数据最大是10⁴，所以我尝试了一下O(n²)的模拟方式，在java下是可以通过的。 同时可以采用转换的方式，将大于8个小时的定义为1，小于等于的定义为-1，则某一段大于1的子段就是符合题意的， 我们只需要从左到右遍历输入，然后累加结果，如果大于1则更新答案，如果小于1则寻找是否存在累加值减1的答案，为了方便保存和获取之前计算的值，我们用 一个map进行数据存储。

数据结构选择

在模拟的情况只需要一个数组进行前缀和存储，在采用数据转换的方法时需要一个map保存累计值和其对应的下标。

题解

//模拟
class Solution {
    public int longestWPI(int[] hours) {
        int max=0,n=hours.length;
        int[] sum=new int[n+1];
        sum[0]=0;
        for(int i=1;i<=n;i++){
            if(hours[i-1]>8){
                sum[i]=sum[i-1]+1;
            }
            else{
                sum[i]=sum[i-1];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=n;j>=i;j--){
                int len=j-i+1;
                if(sum[j]-sum[i-1]>len/2){
                    max=Math.max(len,max);
                    break;
                }
            }
        }
        return max;
    }
}
//数据映射 >8->1 <8->-1 来自leetcode官网
class Solution {
    public int longestWPI(int[] hours) {
        int n = hours.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int s = 0, res = 0;
        for (int i = 0; i < n; i++) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) {
                res = Math.max(res, i + 1);
            } else {
                if (map.containsKey(s - 1)) {
                    res = Math.max(res, i - map.get(s - 1));
                }
            }
            if (!map.containsKey(s)) {
                map.put(s, i);
            }
        }
        return res;
    }
}