健身计划评估
难度:
标签:
题目描述
代码结果
运行时间: 36 ms, 内存: 26.8 MB
/*
* Leetcode 1176: 健身计划评估
* 题目思路:
* 给定一个整数数组 calories 和一个整数 k,
* 求在任意连续的 k 天中,卡路里总和严格大于 upper 的子数组数量和严格小于 lower 的子数组数量之和。
*
* 使用Java Stream实现:
* 1. 使用IntStream对数组进行滑动窗口处理。
* 2. 通过sum函数计算每个窗口的卡路里总和。
* 3. 过滤出总和大于 upper 或者小于 lower 的窗口。
* 4. 计数并返回结果。
*/
import java.util.stream.IntStream;
public class Solution {
public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
return (int) IntStream.rangeClosed(0, calories.length - k)
.mapToObj(i -> IntStream.range(i, i + k).map(j -> calories[j]).sum())
.filter(sum -> sum > upper || sum < lower)
.count();
}
}
解释
方法:
本题解采用滑动窗口和前缀和的方法来解决问题。首先计算出所有卡路里的前缀和数组 cumsum,其中 cumsum[i] 表示从开始到第 i-1 个元素的卡路里总和。这样,任意长度为 k 的子数组的卡路里和可以通过 cumsum[i+k] - cumsum[i] 快速计算得出,避免了重复计算。接着,遍历数组,对于每个长度为 k 的连续子数组,比较其卡路里总和与给定的 lower 和 upper 值,根据比较结果更新得分。如果总和小于 lower,则将 score 减一,如果大于 upper,则将 score 加一。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在构建前缀和数组时,数组的长度设置为 `n + k` 而不是仅为 `n`?
▷🦆
在计算子数组卡路里总和时,使用 `cumsum[i + k] - cumsum[i]` 表达式的正确性是基于什么假设?
▷🦆
前缀和数组 `cumsum` 的初始化为什么从索引1开始计算而非索引0?
▷🦆
如何处理数组 `calories` 的长度小于 k 的情况,这种情况下如何计算得分?
▷