题目描述
你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。
他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。
为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他 「这一天以及之后的连续几天」 （共 k 天）内消耗的总卡路里 T：
- 如果
T < lower，那么这份计划相对糟糕，并失去 1 分；
- 如果
T > upper，那么这份计划相对优秀，并获得 1 分；
- 否则，这份计划普普通通，分值不做变动。
请返回统计完所有 calories.length 天后得到的总分作为评估结果。
注意：总分可能是负数。
示例 1：
输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
输出：0
解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.
示例 2：
输入：calories = [3,2], k = 2, lower = 0, upper = 1
输出：1
解释：calories[0] + calories[1] > upper, 总分 = 1.
示例 3：
输入：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^50 <= calories[i] <= 200000 <= lower <= upper
解法
方法一：前缀和
我们先预处理出长度为 $n+1$ 的前缀和数组 $s$，其中 $s[i]$ 表示前 $i$ 天的卡路里总和。
然后遍历前缀和数组 $s$，对于每个位置 $i$，计算 $s[i+k]-s[i]$，即为第 $i$ 天开始的连续 $k$ 天的卡路里总和。根据题意，对于每个 $s[i+k]-s[i]$，判断值与 $lower$ 和 $upper$ 的关系，更新答案即可。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 calories 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def dietPlanPerformance(
self, calories: List[int], k: int, lower: int, upper: int
) -> int:
s = list(accumulate(calories, initial=0))
ans, n = 0, len(calories)
for i in range(n - k + 1):
t = s[i + k] - s[i]
if t < lower:
ans -= 1
elif t > upper:
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
int n = calories.length;
int[] s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + calories[i];
}
int ans = 0;
for (int i = 0; i < n - k + 1; ++i) {
int t = s[i + k] - s[i];
if (t < lower) {
--ans;
} else if (t > upper) {
++ans;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public:
int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
int n = calories.size();
int s[n + 1];
s[0] = 0;
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + calories[i];
}
int ans = 0;
for (int i = 0; i < n - k + 1; ++i) {
int t = s[i + k] - s[i];
if (t < lower) {
--ans;
} else if (t > upper) {
++ans;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
n := len(calories)
s := make([]int, n+1)
for i, x := range calories {
s[i+1] = s[i] + x
}
for i := 0; i < n-k+1; i++ {
t := s[i+k] - s[i]
if t < lower {
ans--
} else if t > upper {
ans++
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | function dietPlanPerformance(calories: number[], k: number, lower: number, upper: number): number {
const n = calories.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + calories[i];
}
let ans = 0;
for (let i = 0; i < n - k + 1; ++i) {
const t = s[i + k] - s[i];
if (t < lower) {
--ans;
} else if (t > upper) {
++ans;
}
}
return ans;
}
|
方法二：滑动窗口
我们维护一个长度为 $k$ 的滑动窗口，窗口内元素之和记为 $s$。如果 $s \lt lower$，则分数减 $1$；如果 $ s \gt upper$，则分数加 $1$。
时间复杂度 $O(n)$，其中 $n$ 为数组 calories 的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def dietPlanPerformance(
self, calories: List[int], k: int, lower: int, upper: int
) -> int:
def check(s):
if s < lower:
return -1
if s > upper:
return 1
return 0
s, n = sum(calories[:k]), len(calories)
ans = check(s)
for i in range(k, n):
s += calories[i] - calories[i - k]
ans += check(s)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
int s = 0, n = calories.length;
for (int i = 0; i < k; ++i) {
s += calories[i];
}
int ans = 0;
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
for (int i = k; i < n; ++i) {
s += calories[i] - calories[i - k];
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
int n = calories.size();
int s = accumulate(calories.begin(), calories.begin() + k, 0);
int ans = 0;
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
for (int i = k; i < n; ++i) {
s += calories[i] - calories[i - k];
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
n := len(calories)
s := 0
for _, x := range calories[:k] {
s += x
}
if s < lower {
ans--
} else if s > upper {
ans++
}
for i := k; i < n; i++ {
s += calories[i] - calories[i-k]
if s < lower {
ans--
} else if s > upper {
ans++
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function dietPlanPerformance(calories: number[], k: number, lower: number, upper: number): number {
const n = calories.length;
let s = calories.slice(0, k).reduce((a, b) => a + b);
let ans = 0;
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
for (let i = k; i < n; ++i) {
s += calories[i] - calories[i - k];
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
}
return ans;
}
|