电子商务网站建设 上海,那里有做网站,海报生成免费,开发公司质量安全科职责表现良好的最长时间段
难度#xff1a;中等
给你一份工作时间表 hours#xff0c;上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候#xff0c;那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」#xff0c;意味在这…表现良好的最长时间段
难度中等
给你一份工作时间表 hours上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」意味在这段时间内「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1
输入hours [9,9,6,0,6,6,9]
输出3
解释最长的表现良好时间段是 [9,9,6]。示例 2
输入hours [6,6,6]
输出0前置知识前缀和
对于数组 nums\textit{nums}nums定义它的前缀和 s[0]0\textit{s}[0]0s[0]0s[i1]∑j0inums[j]。\textit{s}[i1] \sum\limits_{j0}^{i}\textit{nums}[j]。s[i1]j0∑inums[j]。 例如 nums[1,2,−1,2]\textit{nums}[1,2,-1,2]nums[1,2,−1,2]对应的前缀和数组为 s[0,1,3,2,4]s[0,1,3,2,4]s[0,1,3,2,4]。
通过前缀和我们可以把子数组的元素和转换成两个前缀和的差即
∑jleftrightnums[j]∑j0rightnums[j]−∑j0left−1nums[j]s[right1]−s[left]\sum_{j\textit{left}}^{\textit{right}}\textit{nums}[j] \sum\limits_{j0}^{\textit{right}}\textit{nums}[j] - \sum\limits_{j0}^{\textit{left}-1}\textit{nums}[j] \textit{s}[\textit{right}1] - \textit{s}[\textit{left}] jleft∑rightnums[j]j0∑rightnums[j]−j0∑left−1nums[j]s[right1]−s[left] 例如 nums\textit{nums}nums的子数组 [2,−1,2][2,-1,2][2,−1,2] 的和就可以用 s[4]−s[1]4−13s[4]-s[1]4-13s[4]−s[1]4−13 算出来。 注为方便计算常用左闭右开区间 [left,right)[\textit{left},\textit{right})[left,right) 来表示子数组此时子数组的和为 s[right]−s[left]\textit{s}[\textit{right}] - \textit{s}[\textit{left}]s[right]−s[left]子数组的长度为 right−left\textit{right}-\textit{left}right−left。 方法一单调栈
思路
先把问题转换到我们熟悉的东西上。
「劳累天数大于不劳累天数」等价于「劳累天数减去不劳累天数大于 000」。
那么把劳累的一天视作 nums[i]1\textit{nums}[i]1nums[i]1不劳累的一天视作 nums[i]−1\textit{nums}[i]-1nums[i]−1则问题变为
计算 nums\textit{nums}nums 的最长子数组其元素和大于 000。
既然说到了「子数组的元素和」那么利用前缀和 sss将问题变为
找到两个下标 iii 和 jjj满足 jijiji 且 s[j]s[i]s[j]s[i]s[j]s[i]最大化 i−ji-ji−j 的值。
想一想哪些值可以作为 jjj最长子数组的左端点呢 复杂度分析
时间复杂度 O(n)O(n)O(n)其中 nnn 为 hours\textit{hours}hours的长度。注意每个元素至多入栈出栈各一次因此二重循环的时间复杂度是 O(n)O(n)O(n) 的。空间复杂度 O(n)O(n)O(n)。
class Solution:def longestWPI(self, hours: List[int]) - int:hours_sum, start [0] * (len(hours) 1), [0]for i in range(len(hours)):# 前缀和hours_sum[i1] hours_sum[i] 1 if hours[i] 8 else hours_sum[i] - 1# 可能是开头的位置if hours_sum[start[-1]] hours_sum[i1]:start.append(i1)res 0for i in range(len(hours), 0, -1):while start and hours_sum[i] hours_sum[start[-1]]:res max(res, i - start.pop())return res方法二利用前缀和的连续性
虽说方法一更加通用不过利用 nums\textit{nums}nums中只有 111 和 −1−1−1 的特点可以做到一次遍历。
考虑 s[i]s[i]s[i]
如果 s[i]0s[i]0s[i]0那么 j0j0j0 就是最远的左端点因为 s[0]0s[0]0s[0]0故 s[i]−s[0]s[i]0s[i]-s[0]s[i]0s[i]−s[0]s[i]0符合要求。如果 s[i]≤0s[i]\le 0s[i]≤0那么 jjj 就是 s[i]−1s[i]-1s[i]−1 首次出现的位置。为什么是 s[i]−1s[i]-1s[i]−1 而不是其它更小的数这是因为前缀和是从 000 开始的由于 nums\textit{nums}nums 中只有 111 和 −1−1−1那么相邻前缀和的差都恰好为 111要想算出比 s[i]−1s[i]-1s[i]−1 更小的数必然会先算出 s[i]−1s[i]-1s[i]−1那么这些更小数必然在 s[i]−1s[i]-1s[i]−1 首次出现的位置的右边。
代码实现时可以用哈希表记录每个 s[i]s[i]s[i] 首次出现的下标。
不过由于我们只需要考虑值在闭区间 [−n,0][-n,0][−n,0] 内的前缀和用数组记录是更加高效的。同时为了避免用负数访问数组可以在计算过程中把前缀和取反。
复杂度分析
时间复杂度 O(n)O(n)O(n)其中 nnn 为 hours\textit{hours}hours的长度。空间复杂度 O(n)O(n)O(n)。
class Solution:def longestWPI(self, hours: List[int]) - int:pos [0] * (len(hours) 2) # 记录前缀和首次出现的位置res sums 0for i, j in enumerate(hours, 1):sums -1 if j 8 else 1 # 取反改为减法if sums 0:res ielse:if pos[sums1]: # 原本是 sums-1取反改为 sums1res max(res, i-pos[sums1]) # 这里手写 if 会更快if pos[sums] 0:pos[sums] ireturn res来源力扣LeetCode 链接https://leetcode.cn/problems/longest-well-performing-interval/solutions/2110211/liang-chong-zuo-fa-liang-zhang-tu-miao-d-hysl/
