表现良好的最长时间段【LC1124】
给你一份工作时间表
hours，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于
8小时的时候，那么这一天就是「劳累的一天」。所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
下文为自己的题解总结，参考其他题解写成，取其精华，做以笔记，如有描述不清楚或者错误麻烦指正，不胜感激，不喜勿喷！
2023/2/14
看了提示还是只能双层循环 哎…
思路：
首先构造新的数组及其前缀和数组，新数组中将工作时长大于8的记为1，工作时长小于等于8的记为-1，并求出它的前缀和数组，那么题意可以转化为⌈和严格大于0的连续子数组的最大长度⌋ 那么可以通过三种方法求出⌈和严格大于0的连续子数组的最大长度⌋
暴力
哈希表
单调栈
实现：暴力
class Solution { public int longestWPI(int[] hours) { int n = hours.length; int[] preSum = new int[n + 1]; int res = 0; for (int i = 0; i < n; i++){ preSum[i + 1] = hours[i] > 8 ? preSum[i] + 1 : preSum[i] - 1; } for (int i = 0; i < n; i++){ for (int j = i + 1; j <= n; j++){ if (preSum[j] - preSum[i] > 0){ res = Math.max(res, j - i); } } } return res; } }
复杂度
- 时间复杂度：O(n2)
空间复杂度：O(n2)
实现：哈希表
- 由于新数组中的值只存在1和-1，因此相邻前缀和的差恰好为1
- 利用前缀和数组的性质可得
当p r e S u m [ i ] > 0 时，最远的左端点即为j = 0
当p r e S u m [ i ] < = 0 时，最远的左端点即为j 为p r e S u m [ i ] − 1 首次出现的位置
实现时，使用变量代替前缀和数组
class Solution { public int longestWPI(int[] hours) { int n = hours.length; int preSum = 0; Map<Integer, Integer> map = new HashMap<>(); int res = 0; for (int i = 0; i < n; i++){ preSum += hours[i] > 8 ? 1 : -1; if (preSum > 0){ res = Math.max(res, i + 1); }else if (map.containsKey(preSum - 1)){ res = Math.max(i - map.get(preSum - 1), res); } if (!map.containsKey(preSum)){ map.put(preSum, i); } } return res; } }
class Solution { public int longestWPI(int[] hours) { int n = hours.length, ans = 0, s = 0; var pos = new int[n + 2]; // 记录前缀和首次出现的位置 for (int i = 1; i <= n; ++i) { s -= hours[i - 1] > 8 ? 1 : -1; // 取反，改为减法 if (s < 0) ans = i; else { if (pos[s + 1] > 0) ans = Math.max(ans, i - pos[s + 1]); if (pos[s] == 0) pos[s] = i; } } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/longest-well-performing-interval/solutions/2110211/liang-chong-zuo-fa-liang-zhang-tu-miao-d-hysl/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O ( n )
空间复杂度：O(n)
实现：单调栈
class Solution { public int longestWPI(int[] hours) { int n = hours.length, ans = 0; var s = new int[n + 1]; // 前缀和 var st = new ArrayDeque<Integer>(); st.push(0); // s[0] for (int j = 1; j <= n; ++j) { s[j] = s[j - 1] + (hours[j - 1] > 8 ? 1 : -1); if (s[j] < s[st.peek()]) st.push(j); // 感兴趣的 j } for (int i = n; i > 0; --i) while (!st.isEmpty() && s[i] > s[st.peek()]) ans = Math.max(ans, i - st.pop()); // [栈顶,i) 可能是最长子数组 return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/longest-well-performing-interval/solutions/2110211/liang-chong-zuo-fa-liang-zhang-tu-miao-d-hysl/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O ( n )
空间复杂度：O ( n ) O(n)
