题目描述
calories[i]
给出了健身者在第 i
天需要消耗的卡路里总量,对于每连续的 k
天,消耗的总卡路里为 T:
- 如果
T < lower
,那么这份计划相对糟糕,并失去 1 分; - 如果
T > upper
,那么这份计划相对优秀,并获得 1 分; - 否则,分值不做变动。
请返回统计完所有 calories.length
天后得到的总分作为评估结果。
注意:总分可能是负数。
样例
输入:calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
输出:0
解释:calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.
输入:calories = [3,2], k = 2, lower = 0, upper = 1
输出:1
解释:calories[0] + calories[1] > upper, 总分 = 1.
输入:calories = [6,5,0,0], k = 2, lower = 1, upper = 5
输出:0
解释:calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 总分 = 0.
限制
1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper
算法
(线性扫描) $O(n)$
- 线性扫描数组,每次
sum
累计当前的卡路里,去掉k
天之前的卡路里,然后进行判断。
时间复杂度
- 仅扫描一遍数组,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要额外的常数空间,故空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
int tot = 0, sum = 0, n = calories.size();
for (int i = 0; i < n; i++) {
sum += calories[i];
if (i >= k)
sum -= calories[i - k];
if (i >= k - 1) {
if (sum < lower)
tot--;
else if (sum > upper)
tot++;
}
}
return tot;
}
};