跳转至

1176. 健身计划评估 🔒

题目描述

你的好友是一位健身爱好者。前段日子,他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。

他会有一份计划消耗的卡路里表,其中 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^5
  • 0 <= calories[i] <= 20000
  • 0 <= 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;
}

评论