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

Leetcode.1124 表现良好的最长时间段

题目链接

Leetcode.1124 表现良好的最长时间段 Rating : 1908

题目描述

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

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

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

示例 1:

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

示例 2:

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

提示

  • 1<=hours.length<=1041 <= hours.length <= 10^41<=hours.length<=104
  • 0<=hours[i]<=160 <= hours[i] <= 160<=hours[i]<=16

分析:

问题转化工作时间大于8h 看作+1工作时间 小于等于 8h 看作 -1。所以原问题转化为 求一段连续的区间 [l,r],这个区间和是大于0的,且区间长度最大

我们用 前缀和 可以在 O(1)O(1)O(1) 的复杂度求出一段连续区间的和。

如果我们暴力枚举 n-1个左端点,寻找最长的区间和sum > 0的区间,会超时…

为此我们使用一个 单调栈 来记录,所有可能的左端点。

在这里插入图片描述
当遍历到 s[i]s[i]s[i] 时,如果 s[j]<s[i]s[j] < s[i]s[j]<s[i],说明 s[j]s[j]s[j] 就可能称为一个左端点。

如果想让 s[i]s[i]s[i] 也有成为左端点的可能,后面必然有一个 s[k]>s[i]s[k] > s[i]s[k]>s[i],但是这样的话 s[k]>s[j]s[k] > s[j]s[k]>s[j]s[i]s[i]s[i] 相比 s[j]s[j]s[j] 更可能成为一个左端点。

所以栈 stk中,要记录的就是这样的点,栈中的元素是从 栈底到栈顶 依次递减的。

最后,我们倒序遍历 前缀和数组s,如果当前的s[i]大于 栈顶元素 s[stk.top()],就更新最大值。

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

代码:

class Solution {
public:int longestWPI(vector<int>& hours) {int n = hours.size();//前缀和数组int s[n+1];s[0] = 0;stack<int> st;//先插入0,处理边界情况st.push(0);for(int i = 1;i <= n;i++){s[i] = s[i-1] + (hours[i-1] > 8 ? 1 : -1);if(s[st.top()] > s[i]) st.push(i);}int ans = 0;for(int i = n;i >= 1;--i){while(!st.empty() && s[i] > s[st.top()]){ans = max(ans , i - st.top());st.pop();}}return ans;}
};
http://www.lryc.cn/news/7041.html

相关文章:

  • 达梦数据库会话、事务阻塞排查步骤
  • sqlServer 2019 开发版(Developer)下载及安装
  • 使用Arthas定位问题
  • 性能测试之tomcat+nginx负载均衡
  • 【手写 Vuex 源码】第十一篇 - Vuex 插件的开发
  • opencv基础知识和绘图图形
  • 15- 决策回归树, 随机森林, 极限森林 (决策树优化) (算法)
  • Flink相关的记录
  • 配置可视化-基于form-render的无代码配置服务(一)
  • Java 代理模式详解
  • 知识付费小程序怎么做_分享知识付费小程序的作用
  • 14- 决策树算法 (有监督学习) (算法)
  • 如何编译和运行C++程序?
  • Golang 给视频添加背景音乐 | Golang工具
  • 让AI护理医疗:解决卫生系统的痛点
  • Windows 离线安装 MySQL 8
  • 【前端攻城狮之vue基础】02路由+嵌套路由+路由query/params传参+路由props配置+replace属性+编程式路由导航+缓存路由组件
  • CHAPTER 1 Zabbix介绍及安装
  • 认识V模型、W模型、H模型
  • excel ttest检测
  • PDFPrinting.Net操作进行细粒度控制
  • SegPGD
  • ESP-IDF + Vscode ESP32 开发环境搭建以及开发入门
  • SpringMvc的请求和响应
  • 【Vue3】首页主体-面板组件封装
  • 部署 K8s 集群
  • 关于北京君正:带ANC的2K网络摄像头用户案例
  • ccc-Backpropagation-李宏毅(7)
  • 找出字符串中第一个匹配项的下标-力扣28-java
  • SpringBoot 监听Redis key过期回调