算法随笔_51: 表现良好的最长时间段_方法2

上一篇:算法随笔_50: 表现良好的最长时间段-CSDN博客

=====

题目描述如下:

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

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

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

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

示例 1：

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

示例 2：

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

=====

在上一篇里我们介绍了解决这道算法题的一个方法:前缀和。这一篇我们介绍另外一种方法: 单调栈。

其实这个方法我们可以从上一篇的算法引申而来。上一篇我们是固定右端点，寻找其最左端点。这一篇，我们固定左端点，寻找其最右端点。

我们再来回顾一下上一篇的字典sum2ind，sum2ind[pre_sum]=i，表示前缀和pre_sum第一次出现在索引 i 处。

我们尝试固定sum2ind[pre_sum]为左端点，找到它所对应的最右端点。那么sum2ind[pre_sum]所起始的一个最长区间就找到了。我们枚举所有的sum2ind[pre_sum]，找出它们各自的最右端点。最后取它们长度的最大值即为最终答案。下面我们看看如何找到它们的最右端点。

很显然，sum2ind[pre_sum]的最右端点必然出现在从右往左枚举数组碰到的第一个大于pre_sum的所在索引处。

sum2ind所有的pre_sum键都是小于等于0的。且必然是先出现-1，然后-2，-3等等，以此类推。因此我们只需要维护一个单调栈来存储这些第一次出现的小于0的前缀和所在的索引。我们从左往右遍历原数组。对于出现的大于栈顶的元素的前缀和都可以抛弃。单调栈里的元素，因为存储的是索引，因此，往栈顶方向维持一个递增的趋势。但索引对应的前缀和是一个递减的趋势。

一次遍历后，stck里面的元素就是我们需要探寻的所有左端点。我们从右往左枚举原数组hours，找到以stck栈顶元素为左端点的最右端点比如索引 i 。然后弹出栈顶元素，继续从i 处往左遍历。

这里可能需要解释一下，继续从i 处往左遍历的话对于新的栈顶元素不会遗漏最优解吗？为什么无需从数组末端重新枚举？

比如我们找到了stck[-1]的最右端点在索引 i 处。那么索引 i 的右侧所有索引的pre_sum都小于等于stck[-1]的pre_sum，又因为stck[-1]的pre_sum比stck[-2]的pre_sum小，所以stck[-2]的最右端点不可能在索引 i 的右侧。

最后在代码实现的时候，我们把pre_sum设为一个数组，数组的长度为原数组的长度加1，pre_sum的起始元素我们设为0，从pre_sum[1]处开始对应hours[0]，以此类推。

算法的时间复杂度为O(n)。下面是代码实现:

class Solution(object):
    def longestWPI(self, hours):
        """
        :type hours: List[int]
        :rtype: int
        """
        hours_len=len(hours)
        pre_sum = [0]*(hours_len+1)
        stck=[0]
        
        for i in range(hours_len):
            pre_sum[i+1]= pre_sum[i] + (1 if hours[i] > 8 else -1)
            if pre_sum[i+1] < pre_sum[stck[-1]]:
                stck.append(i+1)
                
        res=0
        for i in range(hours_len, 0, -1):
            while stck and pre_sum[i] > pre_sum[stck[-1]]:
                res=max(res, i-stck.pop())
        return res

关键词: 单调栈