题目描述

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

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

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

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

示例 1：

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

做法

前缀和+单调栈求解
具体做法参见这里

C++ 代码

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        vector<int> sum(hours.size() + 1);
        sum[0] = 0;
        for (int i = 1; i <=hours.size(); i++) {
            sum[i] = sum[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
        }
        stack<int> st;
        int longest = 0;
        for(int i = 0;i<sum.size();i++){
            if (st.empty() || sum[i] < sum[st.top()]) { st.push(i); }
        }
        for(int i = sum.size()-1;i>=0;i--){
            while (!st.empty() && sum[i] > sum[st.top()]) {
                int top = st.top(); st.pop();
                longest = max(longest, i - top);
            }
        }
        return longest;
    }
};