算法

算法

算法总结

• 单调栈
• • 上坡问题
  • • 1.2021-4-13 前缀和+单调栈

单调栈

上坡问题

1.2021-4-13 前缀和+单调栈

题目：

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。请你返回「表现良好时间段」的最大长度。

示例1

输入

hours = [9,9,6,0,6,6,9]

输出

3

解释

最长的表现良好时间段是 [9,9,6]。	

思路：

首先将处理原数组，>8改成1,<=8改成-1。
再得到前缀和数组，比如：
原数组：9 9 6 0 6 6 9
前缀和：0 1 2 1 0 -1 -2 -1
那么问题就转成了上坡问题：当sum[i]<sum[j]时，j-i的最大值。
我们通过维护一个单调递减的栈，把0 -1 -2对应的下标放到栈中，即0 5 6。
随后从后往前遍历保证下标差最大，每次sum[i]如果大于栈头元素，则出栈并更新j-i最大值。
这里可能会有疑问：为什么要存0 -1 -2 ，-2 -1后的-1不是也可以存嘛？
这是因为第二个-1作为i比第一个-1要更右，因此j-i时会更小，不需要放进来。

代码：

    int longestWPI(vector<int>& hours) {int ans=0;int n=hours.size();for(auto&e:hours){if(e>8)e=1;else e=-1; }vector<int> sum(n+1,0);for(int i=1;i<=n;++i)sum[i]=sum[i-1]+hours[i-1];stack<int> s;s.push(0);for(int i=1;i<=n;++i){int nowtop=p()];if(sum[i]<nowtop)s.push(i);}for(int i=n;i>=0;--i){while(s.size()!=0&&sum[i]>p()]){ans=max(p());s.pop();}}return ans;}