【LeetCode】每日一题（4）

目录

题目：1124. 表现良好的最长时间段 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

---

题目：1124. 表现良好的最长时间段 - 力扣（Leetcode）

题目的接口：

class Solution {
public:int longestWPI(vector<int> &hours) {}
};

解题思路：

这题好难，我之前没做过这样类似的题型，还是刷题刷少了，

这次全靠大神题解救我一命，但也有好多看不懂的操作。

废话不多说：

这题用的是前缀和以及单调栈的思路：

我们建一个vector计算前缀和：

思路是：如果工作小时大于8就看成1，工作小时小于8就看成-1。

然后维护一个递减的单调栈，每次将更远的区间位置push进去。

最后逆序迭代前缀和数组，与单调栈中的最远区间位置对比，

通过相减计算最远距离，最后返回即可。

代码：

class Solution {
public:int longestWPI(vector<int> &hours) {int n = hours.size();//建一个vector用来存储前缀和vector<int> v(n + 1, 0);//建立并维护一个单调递减的栈stack<int> st;st.push(0);//遍历整个数组for(int i = 1;i <= n;i++){//计算前缀和v[i] = (hours[i - 1] - 8 > 0 ? 1 : -1) + v[i - 1];//当出现更远距离的时候push进去if(v[st.top()] > v[i]){st.push(i);}}int ans = 0;//倒序遍历前缀数组for(int j = n;j >= 0;j--){while(!st.empty() && v[j] > v[st.top()]){//计算最大距离ans = max(ans, j - st.top());st.pop();}}return ans;}
};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。