青岛开发区网站建设服务,宜宾公司做网站,php网站开发小程序,网页制作网站花店表现良好的最长时间段【LC1124】 给你一份工作时间表 hours#xff0c;上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候#xff0c;那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」#xff0c;意味在这段时间内#…表现良好的最长时间段【LC1124】 给你一份工作时间表 hours上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」意味在这段时间内「劳累的天数」是严格 大于「不劳累的天数」。 请你返回「表现良好时间段」的最大长度。 下文为自己的题解总结参考其他题解写成取其精华做以笔记如有描述不清楚或者错误麻烦指正不胜感激不喜勿喷 2023/2/14 看了提示还是只能双层循环 哎… 思路 首先构造新的数组及其前缀和数组新数组中将工作时长大于8的记为1工作时长小于等于8的记为-1并求出它的前缀和数组那么题意可以转化为⌈\lceil⌈和严格大于0的连续子数组的最大长度⌋\rfloor⌋那么可以通过三种方法求出⌈\lceil⌈和严格大于0的连续子数组的最大长度⌋\rfloor⌋ 暴力哈希表单调栈 实现暴力 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(n^2)O(n2)空间复杂度O(n)O(n)O(n) 实现哈希表 由于新数组中的值只存在1和-1因此相邻前缀和的差恰好为1利用前缀和数组的性质可得 当preSum[i]0preSum[i]0preSum[i]0时最远的左端点即为j0j 0j0当preSum[i]0preSum[i]0preSum[i]0时最远的左端点即为jjj为preSum[i]−1preSum[i]-1preSum[i]−1首次出现的位置 实现时使用变量代替前缀和数组 class Solution {public int longestWPI(int[] hours) {int n hours.length;int preSum 0;MapInteger, 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)O(n)空间复杂度O(n)O(n)O(n) 实现单调栈 当s[j]s[i]s[j] s[i]s[j]s[i]时jjj可以作为左端点而我们要求最大长度因此应该尽可能让jjj位于左端点因此可以使用单调递减栈存放preSum中递减元素的下标而如果存在s[r1]s[r2],r1r2s[r_1]s[r_2],r_1r_2s[r1]s[r2],r1r2的情况时r1r_1r1一定不是最远的右端点因为存在一个左端点满足s[l]s[r1]s[r2],lr1r2s[l]s[r_1]s[r_2],lr_1r_2s[l]s[r1]s[r2],lr1r2那么此时最长子数组区间为[l,r2][l,r_2][l,r2]因此为了避免再次将元素放入栈中我们可以选择倒序遍历右端点 class Solution {public int longestWPI(int[] hours) {int n hours.length, ans 0;var s new int[n 1]; // 前缀和var st new ArrayDequeInteger();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)空间复杂度O(n)O(n)O(n)
