表现良好的最长时间段

题目

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

---

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

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

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= hours.length <= 10^4
• 0 <= hours[i] <= 16

题解

方法一：

思路

我们将hours二值化。对于hours[i]>8则hours[i] = 1，否则hours[i] = -1。

对于「表现良好的时间段」，其实就是区间和至少为1。

为了快速得到区间和，可以用前缀数组。

设p[i]为前i个数的最大值。即p[0] = 0, p[i] = p[i-1] + hours[i-1]

此时对于任意p[j]-p[i]>=1的区间[i,j]，都是「表现良好的时间段」。

如果我们固定右端点j，枚举左端点i，则可以在O(n^2)时间复杂度找到答案。

又没有快速找到最优的左端点的方法呢？

显然对于右端点j，最优的左端点应该是满足p[i] < p[j]最小的i。

可以用树状数组加快查询，不过p[i]存在非正数，需要离散化。
将离散化的前缀和作为树状数组的下标，前缀数组的下标作为树状数组的值，维护最小值。即可。

代码

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int longestWPI(vector<int>& h) {
        int n = h.size();
        vector<int> p(n+1);
        for (int i=1; i<=n; i++) {
            p[i] = p[i-1] + (h[i-1]>8?1:-1);
        }

        map<int,int> id;
        for (int i=0; i<=n; i++) {
            id[p[i]];
            id[p[i]-1];
        }
        int sz = 1;
        for (auto& [i,j]:id) j = sz++;

        vector<int> a(sz, INF);
        auto ask = [&](int x) {
            int rt = INF;
            for (int i=x; i; i-=i&-i) {
                rt = min(rt, a[i]);
            }
            return rt;
        };
        auto add = [&](int x, int val) {
            for (int i=x; i<sz; i+=i&-i) {
                a[i] = min(a[i], val);
            }
        };
        add(id[0], 0);
        int ans = 0;
        for (int i=1; i<=n; i++) {
            ans = max(ans, i-ask(id[p[i]-1]));
            add(id[p[i]], i);
        }
        return ans;
    }
};

方法二：

思路

巧妙的单调栈。

考虑哪些可以作为区间左端点，若i可以作为左端点，那么作为左端点的j（j < i），满足p[j]>p[i]。
若p[j]<p[i]，后续的右端点可以选择j，这样宽度更大。

因此可以作为左端点的值单调递减，我们将其存入栈中，设栈顶元素为top.

然后从右向左遍历寻找右端点。对于遍历的j，若p[j] > p[top]，更新答案，并移除栈顶。
j之前的元素i即便p[i]>p[top]，由于j靠后，i更新的答案也不如j优，故可以直接删除栈顶。

参考

代码

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        vector<int> p(n+1, 0);
        for (int i=1; i<=n; i++) {
            p[i] = p[i-1] + (hours[i-1]>8?1:-1);
        }
        vector<int> st(1,0);
        for (int i=1; i<=n; i++) {
            if (p[st.back()]>p[i]) {
                st.push_back(i);
            }
        }
        int ans = 0;
        for (int i=n; i>0; i--) {
            while (st.size() && p[st.back()] < p[i]) {
                ans = max(ans, i-st.back());
                st.pop_back();
            }
        }
        return ans;
    }
};