算法刷题打卡第90天:表现良好的最长时间段
表现良好的最长时间段
难度:中等
给你一份工作时间表 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]=0,s[i+1]=∑j=0inums[j]。\textit{s}[i+1] = \sum\limits_{j=0}^{i}\textit{nums}[j]。s[i+1]=j=0∑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]。
通过前缀和,我们可以把子数组的元素和转换成两个前缀和的差,即
∑j=leftrightnums[j]=∑j=0rightnums[j]−∑j=0left−1nums[j]=s[right+1]−s[left]\sum_{j=\textit{left}}^{\textit{right}}\textit{nums}[j] = \sum\limits_{j=0}^{\textit{right}}\textit{nums}[j] - \sum\limits_{j=0}^{\textit{left}-1}\textit{nums}[j] = \textit{s}[\textit{right}+1] - \textit{s}[\textit{left}] j=left∑rightnums[j]=j=0∑rightnums[j]−j=0∑left−1nums[j]=s[right+1]−s[left]
例如 nums\textit{nums}nums的子数组 [2,−1,2][2,-1,2][2,−1,2] 的和就可以用 s[4]−s[1]=4−1=3s[4]-s[1]=4-1=3s[4]−s[1]=4−1=3 算出来。
注:为方便计算,常用左闭右开区间 [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,满足 j<ij<ij<i 且 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[i+1] = hours_sum[i] + 1 if hours[i] > 8 else hours_sum[i] - 1# 可能是开头的位置if hours_sum[start[-1]] > hours_sum[i+1]:start.append(i+1)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,那么 j=0j=0j=0 就是最远的左端点,因为 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[sums+1]: # 原本是 sums-1,取反改为 sums+1res = max(res, i-pos[sums+1]) # 这里手写 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/
相关文章:
算法刷题打卡第90天:表现良好的最长时间段
表现良好的最长时间段 难度:中等 给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」,意味在这…...
Python语言零基础入门教程(十七)
Python 文件I/O 本章只讲述所有基本的 I/O 函数,更多函数请参考Python标准文档。 #### 打印到屏幕 最简单的输出方法是用print语句,你可以给它传递零个或多个用逗号隔开的表达式。此函数把你传递的表达式转换成一个字符串表达式,并将结果写…...
C语言中大小端问题
目录 一、什么是大小端 二、 举个例子 三、大小端演示 四、解释"二"中举例的问题 五、怎么判断是大端还是小端 六、一个题目 一、什么是大小端 大端模式(大端字节序存储):就是高位字节数据存放在内存的低地址端ÿ…...
vue2+微前端qiankun从搭建到部署的实践(主子应用切换;集成vue3+vite3子应用)
一、最终效果 二、微前端(qiankun)介绍及为什么选择用微前端,可以看官网 三、目录结构如下 四、具体配置 一、主应用配置 1、主应用技术栈 Vue-cli4搭建项目Vue2Element-Uiqiankun;Vue2Element-Uiqiankun 2、搭建好主项目&…...
怎么代理微信小程序创业?
随着微信的兴起,小程序已经成为了人们生活中不可或缺的一部分。如果你想要创业的话,那么代理微信小程序是一个不错的选择。本文将为大家介绍怎么代理微信小程序创业。 一、什么是微信小程序 微信小程序是一款专为移动设备使用者而设计的应用。它通过扫…...
今天是情人节呐,我利用Python制作了好多表白的东西,快来吧~
今天是情人节那,有没有现在没有对象的宝子,评论里扣个111哈哈 目录 玫瑰 爱心树 丘比特 多彩气球 阿玥的小课堂 一、情人节的由来 二、情人节的来历和意义 玫瑰 局部代码实现如下: # 花瓣1 turtle.left(150) turtle.circle(-90, 70) …...
【Linux】-- 进程信号(处理、内核)
上篇:【Linux】-- 进程信号(认识、应用)_川入的博客-CSDN博客 目录 信号其他相关常见概念 pending handler block 信号处理的过程 sigset_t sigset_t使用 系统接口 sigpending sigprocmask 捕捉方法 sigaction struct sigactio …...
C/【静态通讯录】
🌱博客主页:大寄一场. 🌱系列专栏:C语言学习笔记 😘博客制作不易欢迎各位👍点赞⭐收藏➕关注 前言 往期回顾: C/扫雷 C/N子棋 通讯录作为通讯录地址的书本,当今的通讯录可以涵盖多项…...
万卷书 - 让孩子对自己负责 [The Self-Driven Child]
让孩子对自己负责 The Self-Driven Child - 让你的孩子更加科学合理的掌控自己的生活 简介 《The Self-Driven Child》(2018)解释了我们对孩子的习惯性控制欲,它导致了孩子压力过大、难以合作,以及主观能动性差。本书不提倡这种做法,而是认为我们应该帮助孩子自己做出合适…...
Postman中cookie的操作
在接口测试中,某些接口的调用,需要带入已有Cookie,比如有些接口需要登陆后才能访问。 Postman接口请求使用Cookie有如下两种方式: 1、直接在头域中添加Cookie头域,适用于已经知道请求所用Cookie数据的情况。 2、使用…...
torch.grid_sample
参考: 双线性插值的理论Pytorch grid_sample解析PyTorch中grid_sample的使用方法pytorch中的grid_sample()使用 查阅官方文档,TORCH.NN.FUNCTIONAL.GRID_SAMPLE grid_sample的函数签名如下所示,torch.nn.functional.grid_sample(input, gr…...
前端基于 Docker 的 SSR 持续开发集成环境实践
项目收益 整体开发效率提升20%。加快首屏渲染速度,减少白屏时间,弱网环境下页面打开速度提升40%。 权衡 在选择使用SSR之前,需要考虑以下事项! SSR需要可以运行Node.js的服务器,学习成本相对较高。对于服务器而言&a…...
ARM交叉编译入门及交叉编译第三方库常见问题解析
1. 交叉编译是什么? 交叉编译简单说来,就是编译成果物的地儿不是你运行这个成果物的地儿。最常见的场景,就是我们要编译一个 ARM版本 的可执行程序,但我们编译这个 ARM版本 可执行程序的地方,是在一个 x86_x64 的平台…...
Ruby Web Service 应用 - SOAP4R
什么是 SOAP? 简单对象访问协议(SOAP,全写为Simple Object Access Protocol)是交换数据的一种协议规范。 SOAP 是一种简单的基于 XML 的协议,它使应用程序通过 HTTP 来交换信息。 简单对象访问协议是交换数据的一种协议规范,是一种轻量的、…...
HashMap底层实现原理概述
原文https://blog.csdn.net/fedorafrog/article/details/115478407 hashMap结构 常见问题 在理解了HashMap的整体架构的基础上,我们可以试着回答一下下面的几个问题,如果对其中的某几个问题还有疑惑,那就说明我们还需要深入代码,…...
Linux驱动学习环境搭建
背景常识 一、程序分类 程序按其运行环境分为: 1. 裸机程序:直接运行在对应硬件上的程序 2. 应用程序:只能运行在对应操作系统上的程序 二、计算机系统的层次结构 所有智能设备其实都是计算机,机顶盒、路由器、冰箱、洗衣机、汽…...
Java基础之异常
目录1 异常1.1 异常的概述1.2 常见异常类型1.3 JVM的默认处理方案1.4 编译时异常的处理方式1.4.1 异常处理之 try ... catch ... [ktʃ](捕获异常)1.4.2 异常处理之 throws(抛出异常)1.5 Throwable 的成员方法1.6 编译时异常和运行…...
感慨:大三了,未来该何去何从呢
笔者曾在十一月份通过了字节跳动的三次面试, 但是最终因为疫情原因不能满足公司的入职时间要求, 没有拿到offer。近期也是投递了大量大厂的实习岗, 但是要么已读不回, 要么明确告诉我学历至少要985硕士(天天被阿里cpu)。 说实话一…...
分账系统逻辑
一、说明 主体与业务关系方进行相关利益和支出的分配过程 使用场景: 在分销业务中,主营商户收到用户购买分销商品所支付的款项后,可以通过分账逻辑,与分销商进行佣金结算。在零售、餐饮等行业中,当销售人员完零售等…...
SpringCloud篇——什么是SpringCloud、有什么优缺点、学习顺序是什么
文章目录一、首先看官方解释二、Spring Cloud 的项目的位置三、Spring Cloud的子项目四、Spring Cloud 现状五、spring cloud 优缺点六、Spring Cloud 和 Dubbo 对比七、Spring Cloud 学习路线一、首先看官方解释 Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
嵌入式面试常问问题
以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...
