算法leetcode

力扣1124-表现良好的最长时间段

字数统计: 990字   |   阅读时长: 4分
, ,

摘要: 本文是力扣 1124 的题解，力扣 962 的进阶问题，单调栈的应用。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，在文章 力扣962-最大宽度坡 中我们解决了力扣 962，本文我们看一个更进一步的问题，力扣 1124，属于单调栈和前缀和的综合应用。

$1 题目

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

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

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

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

1
2
3
提示：
1 <= hours.length <= 10000
0 <= hours[i] <= 16

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

$2 题解

算法: 前缀和 + 单调栈

此前的前缀和(状态)中, 小于当前前缀和的最早位置。

对每一天的工作小时数，hours[i]，记录一个状态值: 如果 hours[i] > 8，则状态记为 1，否则状态记为 -1。

这里状态值为 1 表示该天是劳累的一天，-1 表示该天是不劳累的一天。

预处理出状态值序列的前缀和 sums。给定时间范围 [i, j] 的净劳累天数为 sums[j + 1] - sums[i]，按照表现良好时间段的额定义: 「劳累的天数」是严格 大于「不劳累的天数」的，如果净劳累天数 sums[j + 1] - sums[i] > 0，则时间段 [i, j] 是表现良好时间段。

枚举 sums 上的区间范围的左端点 i=0,1,…,n-1, 考虑右端点 j=i+1,i+2,…,n，如果 sums[i] < sums[j]，则 [i+1, j] 就是一段良好时间段，长度为 j - i。进一步地，如果 j 是 [i+1..n] 上满足 sums[i] < sums[j] 的最大的 j，则以 i 为左端点的良好时间段最长就是 j - i。

因此在 sums 上枚举 i 的过程中，我们要提问：sums[i+1..n] 中大于 sums[i] 的最大的位置 j 是多少。这个需求可以用单调栈来完成。

注：后面的用单调栈处理的提问，过程与 力扣962-最大宽度坡 一样。

因为对起点i, 考虑 i 右侧的 $j1 < j2$, 若 $sums[j1] < sums[j2]$, 则j1无用,因为对任意i, 若j1为候选,则j2总会更好,因此可能的右端点为从右到左单调递增的子序列. 同理可能的左端点是从左到右的单调递减的子序列.

先预处理出两个单调栈的元素: 可能的 i 下标和可能的 j 下标, 然后从右往左枚举 veci, 操作 vecj。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        if(hours.empty()) return 0;
        int n = hours.size();
        vector<int> sums(n + 1, 0);
        for(int i = 1; i <= n; ++i)
        {
            if(hours[i - 1] > 8)
                sums[i] = sums[i - 1] + 1;
            else
                sums[i] = sums[i - 1] - 1;
        }

        vector<int> veci, vecj;
        veci.push_back(0);
        int sum = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(sums[i] < sum)
            {
                veci.push_back(i);
                sum = sums[i];
            }
        }
        sum = sums[n];
        vecj.push_back(n);
        for(int j = n - 1; j >= 0; --j)
        {
            if(sums[j] > sum)
            {
                vecj.push_back(j);
                sum = sums[j];
            }
        }

        int ni = veci.size(), nj = vecj.size();
        int j = 0;
        int ans = 0;
        for(int i = ni - 1; i >= 0; --i)
        {
            while(j < nj && sums[vecj[j]] <= sums[veci[i]])
                ++j;
            if(j < nj)
                ans = max(ans, vecj[j] - veci[i]);
        }
        return ans;
    }
};
Share