适合野炊的日子
难度:
标签:
题目描述
代码结果
运行时间: 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的情况,直接将所有天数作为合适的野炊日子返回?
▷🦆
题解中提到使用store数组来记录每天左边连续非递增天数的数量,那么为什么不需要一个类似的数组来记录每天右边连续非递减天数?
▷🦆
在更新left_c和right_c时,如果当前天的安全指数与前一天相同,为什么left_c和right_c都会增加?这是否会影响判断非递增或非递减的准确性?
▷🦆
题解中判断某一天是否适合野炊时,使用的条件是`right_c >= time`和`store[i-time] >= time`,这里的`store[i-time]`为什么能正确代表从i-time到i的非递增天数?
▷