适合野炊的日子

难度: Medium

你和朋友们准备去野炊。给你一个下标从 0 开始的整数数组 security ，其中 security[i] 是第 i 天的建议出行指数。日子从 0 开始编号。同时给你一个整数 time 。

如果第 i 天满足以下所有条件，我们称它为一个适合野炊的日子：

第 i 天前和后都分别至少有 time 天。
第 i 天前连续 time 天建议出行指数都是非递增的。
第 i 天后连续 time 天建议出行指数都是非递减的。

更正式的，第 i 天是一个适合野炊的日子当且仅当：security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

请你返回一个数组，包含所有适合野炊的日子（下标从 0 开始）。返回的日子可以任意顺序排列。

示例 1：

输入：security = [5,3,3,3,5,6,2], time = 2
输出：[2,3]
解释：
第 2 天，我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。
第 3 天，我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。
没有其他日子符合这个条件，所以日子 2 和 3 是适合野炊的日子。

示例 2：

输入：security = [1,1,1,1,1], time = 0
输出：[0,1,2,3,4]
解释：
因为 time 等于 0 ，所以每一天都是适合野炊的日子，所以返回每一天。

示例 3：

输入：security = [1,2,3,4,5,6], time = 2
输出：[]
解释：
没有任何一天的前 2 天建议出行指数是非递增的。
所以没有适合野炊的日子，返回空数组。

提示：

1 <= security.length <= 10⁵
0 <= security[i], time <= 10⁵

Submission

运行时间: 81 ms

内存: 30.8 MB

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        #指针加记忆搜索
        n = len(security)
        ans = []
        if time == 0:
            return [i for i in range(n)]
        if n < time*2+1:
            return ans
        
        store = [0] * n
        left_c = 0
        right_c = 0

        for i in range(1,n):
            if security[i] < security[i-1]:
                left_c +=1
                right_c = 0
            elif security[i] > security[i-1]:
                left_c = 0
                right_c += 1
            else:
                left_c += 1
                right_c += 1
            store[i] = left_c
            if right_c >= time and store[i-time] >= time:
                ans.append(i-time)
        return ans

Explain

这个题解使用了一种指针加记忆搜索的方法。首先，如果time为0，那么每一天都是适合野炊的日子。接着，如果数组长度小于2*time+1，说明没有足够的天数来满足条件，直接返回空数组。然后，我们使用一个数组store来记录每一天左边连续非递增天数的数量。通过遍历security数组，我们更新left_c和right_c来分别记录当前天数左边和右边连续的非递增或非递减天数。如果当前天数右边的连续非递减天数大于等于time，并且当前天数-time天的左边连续非递增天数也大于等于time，那么这一天就是适合野炊的日子。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        ans = []
        if time == 0:
            return [i for i in range(n)]
        if n < time*2+1:
            return ans
        
        store = [0] * n
        left_c = 0
        right_c = 0

        for i in range(1,n):
            if security[i] < security[i-1]:
                left_c +=1
                right_c = 0
            elif security[i] > security[i-1]:
                left_c = 0
                right_c += 1
            else:
                left_c += 1
                right_c += 1
            store[i] = left_c
            if right_c >= time and store[i-time] >= time:
                ans.append(i-time)
        return ans

Explore

当time为0时，表示不需要任何连续的非递增或非递减天数来判断一个天气是否适合野炊。因此，每一天都自然满足条件，无需任何额外的检查。这是为了简化问题，并直接返回所有可能的日子作为结果。

在题解中，右侧的连续非递减天数是通过即时计算的方式（使用right_c变量）来管理的，这是因为我们只需要知道从当前天数开始往后的连续非递减天数，而不需要存储每一天的详细计数。这种处理方式减少了空间复杂度，同时保持了算法的效率。

当当前天与前一天的安全指数相同时，这意味着这一天既不比前一天更危险（非递增），也不比前一天更安全（非递减）。因此，这一天对于左侧的非递增序列和右侧的非递减序列都是一个延续。这种处理确保连续性的计数是准确的，不会影响判断的准确性。

这里的`store[i-time]`实际上记录的是第i-time天的左侧连续非递增天数。当我们检查第i天时，我们希望确保从第i-time天到第i天这个区间内有足够的非递增天数。由于`store`数组只记录了到每一天为止的左侧非递增天数，因此我们用`store[i-time]`来确保从第i-time天开始，往右至少有time天是符合非递增条件的。