leetcode1124

题目描述

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

题目分析

这道题很有意思，首先我们根本就不关心每天具体的工作时间，仅仅关心它是否大于 8，所以只需要用两个标志位就可以用来标记表示每一天的工作时间，很容易联想到的就是 0 和 1。但是对于本题我们需要对两种表示的数量大小关系进行比较，0 和 1 的表示不能让我们进行直观的比较。考虑换成 -1 和 1，这样就可以用元素和来直观地表示元素数量的大小关系了。而元素和的计算很容易想到的办法就是用前缀和， 可以直接由 计算得出。至此，我们的目的就非常清晰了，建立前缀和数组 ，对于所有满足 的 ，找出其中 的最大值。

解决

首先确定候选的左端点 ，采取从前向后的遍历方式，因为我们要求的是 的最大值， 自然要越小越好。对于 ，如果有 ，那么无论何时我们都可以用 替换 得到更大的结果，所以如果我们已经处理过 ，那么在寻找新的候选左端点 的时候只需要考虑 的情况，因为只有这样 才有可能大于 。构建一个单调递减栈 保存候选左端点的索引，首先将 0 压栈，之后遍历遍历数组，当且仅当当前值小于栈顶对应值的时候将当前索引压栈。而对于右端点 ，采取的是从后向前的遍历方式，首先比较 与 的大小，若 则直接将栈顶弹出，循环操作直到栈为空或者 。这一步可以这么理解，如果前面的候选右端点想要有更大的结果则必须找到更靠前的左端点与之配对。如果栈空，则表示已经没有候选左端点了，直接跳出循环。需要注意的是，循环需要维护 这一条件。

代码

#include <bits/stdc++.h>

using namespace std;

int longestWPI(vector<int>& hours) {

    int len = hours.size();

    vector<int> presum(len+1, 0);

    stack<int> stk; stk.emplace(0);

    for(int i = 0; i < len; i++) {

        if(hours[i] > 8) presum[i+1] = presum[i]+1;

        else {

            presum[i+1] = presum[i]-1;

            if(presum[i+1] < presum[stk.top()]) stk.emplace(i+1);

        }

    }

    int ans = 0;

    for(int i = len; i >= 0; i--) {

        if(!stk.empty() && i == stk.top()) stk.pop();

        if(stk.empty()) break;

        if(presum[stk.top()] >= presum[i]) continue;

        int x;

        while(!stk.empty() && presum[stk.top()] < presum[i]) {

            x = stk.top();

            stk.pop();

        }

        ans = max(ans, i-x);

    }

    return ans;

}