当前位置: 首页 > news >正文

算法刷题打卡第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]=0s[i+1]=∑j=0inums[j]。\textit{s}[i+1] = \sum\limits_{j=0}^{i}\textit{nums}[j]。s[i+1]=j=0inums[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=leftrightnums[j]=j=0rightnums[j]j=0left1nums[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]=41=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}rightleft

方法一:单调栈

思路:

先把问题转换到我们熟悉的东西上。

「劳累天数大于不劳累天数」等价于「劳累天数减去不劳累天数大于 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,将问题变为:

找到两个下标 iiijjj,满足 j<ij<ij<is[j]<s[i]s[j]<s[i]s[j]<s[i],最大化 i−ji-jij 的值。

想一想,哪些值可以作为 jjj(最长子数组的左端点)呢?

在这里插入图片描述
复杂度分析:

  • 时间复杂度: O(n)O(n)O(n),其中 nnnhours\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−11 的特点,可以做到一次遍历。

考虑 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−11,那么相邻前缀和的差都恰好为 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),其中 nnnhours\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天:表现良好的最长时间段

表现良好的最长时间段 难度&#xff1a;中等 给你一份工作时间表 hours&#xff0c;上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候&#xff0c;那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」&#xff0c;意味在这…...

Python语言零基础入门教程(十七)

Python 文件I/O 本章只讲述所有基本的 I/O 函数&#xff0c;更多函数请参考Python标准文档。 #### 打印到屏幕 最简单的输出方法是用print语句&#xff0c;你可以给它传递零个或多个用逗号隔开的表达式。此函数把你传递的表达式转换成一个字符串表达式&#xff0c;并将结果写…...

C语言中大小端问题

目录 一、什么是大小端 二、 举个例子 三、大小端演示 四、解释"二"中举例的问题 ​五、怎么判断是大端还是小端 六、一个题目 一、什么是大小端 大端模式&#xff08;大端字节序存储&#xff09;&#xff1a;就是高位字节数据存放在内存的低地址端&#xff…...

vue2+微前端qiankun从搭建到部署的实践(主子应用切换;集成vue3+vite3子应用)

一、最终效果 二、微前端&#xff08;qiankun&#xff09;介绍及为什么选择用微前端&#xff0c;可以看官网 三、目录结构如下 四、具体配置 一、主应用配置 1、主应用技术栈 Vue-cli4搭建项目Vue2Element-Uiqiankun&#xff1b;Vue2Element-Uiqiankun 2、搭建好主项目&…...

怎么代理微信小程序创业?

随着微信的兴起&#xff0c;小程序已经成为了人们生活中不可或缺的一部分。如果你想要创业的话&#xff0c;那么代理微信小程序是一个不错的选择。本文将为大家介绍怎么代理微信小程序创业。 一、什么是微信小程序 微信小程序是一款专为移动设备使用者而设计的应用。它通过扫…...

今天是情人节呐,我利用Python制作了好多表白的东西,快来吧~

今天是情人节那&#xff0c;有没有现在没有对象的宝子&#xff0c;评论里扣个111哈哈 目录 玫瑰 爱心树 丘比特 多彩气球 阿玥的小课堂 一、情人节的由来 二、情人节的来历和意义 玫瑰 局部代码实现如下&#xff1a; # 花瓣1 turtle.left(150) turtle.circle(-90, 70) …...

【Linux】-- 进程信号(处理、内核)

上篇&#xff1a;【Linux】-- 进程信号&#xff08;认识、应用&#xff09;_川入的博客-CSDN博客 目录 信号其他相关常见概念 pending handler block 信号处理的过程 sigset_t sigset_t使用 系统接口 sigpending sigprocmask 捕捉方法 sigaction struct sigactio …...

C/【静态通讯录】

&#x1f331;博客主页&#xff1a;大寄一场. &#x1f331;系列专栏&#xff1a;C语言学习笔记 &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 前言 往期回顾&#xff1a; C/扫雷 C/N子棋 通讯录作为通讯录地址的书本&#xff0c;当今的通讯录可以涵盖多项…...

万卷书 - 让孩子对自己负责 [The Self-Driven Child]

让孩子对自己负责 The Self-Driven Child - 让你的孩子更加科学合理的掌控自己的生活 简介 《The Self-Driven Child》(2018)解释了我们对孩子的习惯性控制欲,它导致了孩子压力过大、难以合作,以及主观能动性差。本书不提倡这种做法,而是认为我们应该帮助孩子自己做出合适…...

Postman中cookie的操作

在接口测试中&#xff0c;某些接口的调用&#xff0c;需要带入已有Cookie&#xff0c;比如有些接口需要登陆后才能访问。 Postman接口请求使用Cookie有如下两种方式&#xff1a; 1、直接在头域中添加Cookie头域&#xff0c;适用于已经知道请求所用Cookie数据的情况。 2、使用…...

torch.grid_sample

参考&#xff1a; 双线性插值的理论Pytorch grid_sample解析PyTorch中grid_sample的使用方法pytorch中的grid_sample()使用 查阅官方文档&#xff0c;TORCH.NN.FUNCTIONAL.GRID_SAMPLE grid_sample的函数签名如下所示&#xff0c;torch.nn.functional.grid_sample(input, gr…...

前端基于 Docker 的 SSR 持续开发集成环境实践

项目收益 整体开发效率提升20%。加快首屏渲染速度&#xff0c;减少白屏时间&#xff0c;弱网环境下页面打开速度提升40%。 权衡 在选择使用SSR之前&#xff0c;需要考虑以下事项&#xff01; SSR需要可以运行Node.js的服务器&#xff0c;学习成本相对较高。对于服务器而言&a…...

ARM交叉编译入门及交叉编译第三方库常见问题解析

1. 交叉编译是什么&#xff1f; 交叉编译简单说来&#xff0c;就是编译成果物的地儿不是你运行这个成果物的地儿。最常见的场景&#xff0c;就是我们要编译一个 ARM版本 的可执行程序&#xff0c;但我们编译这个 ARM版本 可执行程序的地方&#xff0c;是在一个 x86_x64 的平台…...

Ruby Web Service 应用 - SOAP4R

什么是 SOAP&#xff1f; 简单对象访问协议(SOAP,全写为Simple Object Access Protocol)是交换数据的一种协议规范。 SOAP 是一种简单的基于 XML 的协议&#xff0c;它使应用程序通过 HTTP 来交换信息。 简单对象访问协议是交换数据的一种协议规范&#xff0c;是一种轻量的、…...

HashMap底层实现原理概述

原文https://blog.csdn.net/fedorafrog/article/details/115478407 hashMap结构 常见问题 在理解了HashMap的整体架构的基础上&#xff0c;我们可以试着回答一下下面的几个问题&#xff0c;如果对其中的某几个问题还有疑惑&#xff0c;那就说明我们还需要深入代码&#xff0c…...

Linux驱动学习环境搭建

背景常识 一、程序分类 程序按其运行环境分为&#xff1a; 1. 裸机程序&#xff1a;直接运行在对应硬件上的程序 2. 应用程序&#xff1a;只能运行在对应操作系统上的程序 二、计算机系统的层次结构 所有智能设备其实都是计算机&#xff0c;机顶盒、路由器、冰箱、洗衣机、汽…...

Java基础之异常

目录1 异常1.1 异常的概述1.2 常见异常类型1.3 JVM的默认处理方案1.4 编译时异常的处理方式1.4.1 异常处理之 try ... catch ... [ktʃ]&#xff08;捕获异常&#xff09;1.4.2 异常处理之 throws&#xff08;抛出异常&#xff09;1.5 Throwable 的成员方法1.6 编译时异常和运行…...

感慨:大三了,未来该何去何从呢

笔者曾在十一月份通过了字节跳动的三次面试&#xff0c; 但是最终因为疫情原因不能满足公司的入职时间要求&#xff0c; 没有拿到offer。近期也是投递了大量大厂的实习岗&#xff0c; 但是要么已读不回&#xff0c; 要么明确告诉我学历至少要985硕士(天天被阿里cpu)。 说实话一…...

分账系统逻辑

一、说明 主体与业务关系方进行相关利益和支出的分配过程 使用场景&#xff1a; 在分销业务中&#xff0c;主营商户收到用户购买分销商品所支付的款项后&#xff0c;可以通过分账逻辑&#xff0c;与分销商进行佣金结算。在零售、餐饮等行业中&#xff0c;当销售人员完零售等…...

SpringCloud篇——什么是SpringCloud、有什么优缺点、学习顺序是什么

文章目录一、首先看官方解释二、Spring Cloud 的项目的位置三、Spring Cloud的子项目四、Spring Cloud 现状五、spring cloud 优缺点六、Spring Cloud 和 Dubbo 对比七、Spring Cloud 学习路线一、首先看官方解释 Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...