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

LeetCode-1124. 表现良好的最长时间段【哈希表,前缀和,单调栈】

LeetCode-1124. 表现良好的最长时间段【哈希表,前缀和,单调栈】

  • 题目描述:
  • 解题思路一:查字典。cur是当前的前缀和(劳累与不劳累天数之差),向前遍历。有两种情况。情况一,若cur大于0则是[0,i]的劳累与不劳累天数之差一定最大,记录下答案。情况二,若cur小于等于0,用哈希表记录cur(只记录对应最小的)。去哈希表里找到cur-1对应的下标j,那么[j,i]的前缀和为cur-(cur-1)=1>0,记录下答案。
  • 解题思路二:单调栈。将大于8的当做1,小于等于8的当做-1;(劳累与不劳累天数之差)即是s[i]-s[j]。要找大的s[i],小的s[j]
  • 解题思路三:0

题目描述:

给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」,意味在这段时间内,「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1:

输入:hours = [9,9,6,0,6,6,9]
输出:3
解释:最长的表现良好时间段是 [9,9,6]。

示例 2:

输入:hours = [6,6,6]
输出:0

提示:

1 <= hours.length <= 104
0 <= hours[i] <= 16
https://leetcode.cn/problems/longest-well-performing-interval/description/

解题思路一:查字典。cur是当前的前缀和(劳累与不劳累天数之差),向前遍历。有两种情况。情况一,若cur大于0则是[0,i]的劳累与不劳累天数之差一定最大,记录下答案。情况二,若cur小于等于0,用哈希表记录cur(只记录对应最小的)。去哈希表里找到cur-1对应的下标j,那么[j,i]的前缀和为cur-(cur-1)=1>0,记录下答案。

class Solution {
public:int longestWPI(vector<int>& hours) {unordered_map<int,int> index;int cur=0,ans=0,n=hours.size();for(int i=0;i<n;++i){if(hours[i]>8) ++cur;else --cur;if(cur>0) ans=i+1;//cur是[0,i]的劳累与不劳累天数之差,一定最大。else{//cur小于等于0的情况if(index.count(cur-1)>0) ans=max(ans,i-index[cur-1]);//找到cur-1的下标j,则j到i的和是cur-(cur-1)=1>0,cur大于0就判断一下。if(!index.count(cur)) index[cur]=i;//只记录一次,即是前缀和对应下标最小的}}return ans;}
};

时间复杂度:O(n)
空间复杂度:O(n)

解题思路二:单调栈。将大于8的当做1,小于等于8的当做-1;(劳累与不劳累天数之差)即是s[i]-s[j]。要找大的s[i],小的s[j]

class Solution {
public:int longestWPI(vector<int> &hours) {int n=hours.size(),ans=0,s[n+1];//前缀和stack<int> st;st.push(s[0]=0);for(int j=1;j<=n;++j){s[j]=s[j-1]+(hours[j-1]>8?1:-1);//初始化前缀和if(s[j]<s[st.top()]) st.push(j);//感兴趣的j,必然是递减的}for (int i=n;i;--i)while(!st.empty()&&s[i]>s[st.top()]){ans=max(ans,i-st.top());//[栈顶,i)可能是最长子数组st.pop();}//i之前有可能前缀和更大return ans;}
};

时间复杂度:O(n)
空间复杂度:O(n)

解题思路三:0


http://www.lryc.cn/news/6004.html

相关文章:

  • vue-router路由配置
  • 中国计算机设计大赛来啦!用飞桨驱动智慧救援机器狗
  • 嘉定区2022年高新技术企业认定资助申报指南
  • 【C++】关键字、命名空间、输入和输出、缺省参数、函数重载
  • 【一道面试题】关于HashMap的一系列问题
  • 论文笔记: Monocular Depth Estimation: a Review of the 2022 State of the Art
  • Springmvc补充配置
  • MySQL 的 datetime等日期和时间处理SQL函数及格式化显示
  • 基于微信云开发的防诈反诈宣传教育答题小程序
  • Map和Set
  • 【位运算问题】Leetcode 136、137、260问题详解及代码实现
  • 同花顺2023届春招内推
  • 深入Kafka核心设计与实践原理读书笔记第三章消费者
  • IDEA 中使用 Git 图文教程详解
  • 【Linux系统】进程概念
  • 上课睡觉(2023寒假每日一题 4)
  • 【Selenium学习】Selenium 中常用的基本方法
  • python练习——简化路径
  • 2023新华为OD机试题 - 火星文计算2(JavaScript) | 刷完必过
  • 前端插件重磅来袭
  • 深入工厂|高精密多层板是如何被智造出来的?
  • 代理模式动态代理
  • Mysql之二进制日志
  • kail工具的使用--- cewl
  • 【蓝桥杯集训1】前缀和专题(2 / 5)
  • 基于模块联邦的微前端实现方案
  • 【单目标优化算法】食肉植物优化算法(Matlab代码实现)
  • ANTLR4入门学习(四)
  • Android okhttp3中发送websocket消息,并通过mockwebserver将一个安卓设备模拟成服务器接发消息
  • MySQL系统变量和自定义变量