leetcode
leetcode 1851 ~ 1900
适合野炊的日子

适合野炊的日子

难度:

标签:

题目描述

代码结果

运行时间: 81 ms, 内存: 30.8 MB


/* 
 * 思路:
 * 使用Java Stream来实现解决方案。
 * 1. 先过滤掉不满足条件的索引。
 * 2. 再检查剩余索引是否满足非递增和非递减的条件。
 */
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class PicnicDaysStream {
    public List<Integer> goodDaysToGoPicnic(int[] security, int time) {
        int n = security.length;
        return IntStream.range(time, n - time)
                .filter(i -> IntStream.range(i - time, i).allMatch(j -> security[j] >= security[j + 1]))
                .filter(i -> IntStream.range(i, i + time).allMatch(j -> security[j] <= security[j + 1]))
                .boxed()
                .collect(Collectors.toList());
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在题解中,为什么要单独处理time为0的情况,直接将所有天数作为合适的野炊日子返回?
当time为0时,表示不需要任何连续的非递增或非递减天数来判断一个天气是否适合野炊。因此,每一天都自然满足条件,无需任何额外的检查。这是为了简化问题,并直接返回所有可能的日子作为结果。
🦆
题解中提到使用store数组来记录每天左边连续非递增天数的数量,那么为什么不需要一个类似的数组来记录每天右边连续非递减天数?
在题解中,右侧的连续非递减天数是通过即时计算的方式(使用right_c变量)来管理的,这是因为我们只需要知道从当前天数开始往后的连续非递减天数,而不需要存储每一天的详细计数。这种处理方式减少了空间复杂度,同时保持了算法的效率。
🦆
在更新left_c和right_c时,如果当前天的安全指数与前一天相同,为什么left_c和right_c都会增加?这是否会影响判断非递增或非递减的准确性?
当当前天与前一天的安全指数相同时,这意味着这一天既不比前一天更危险(非递增),也不比前一天更安全(非递减)。因此,这一天对于左侧的非递增序列和右侧的非递减序列都是一个延续。这种处理确保连续性的计数是准确的,不会影响判断的准确性。
🦆
题解中判断某一天是否适合野炊时,使用的条件是`right_c >= time`和`store[i-time] >= time`,这里的`store[i-time]`为什么能正确代表从i-time到i的非递增天数?
这里的`store[i-time]`实际上记录的是第i-time天的左侧连续非递增天数。当我们检查第i天时,我们希望确保从第i-time天到第i天这个区间内有足够的非递增天数。由于`store`数组只记录了到每一天为止的左侧非递增天数,因此我们用`store[i-time]`来确保从第i-time天开始,往右至少有time天是符合非递增条件的。

相关问题