Question

1176. 健身计划评估

English Version

题目描述

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

他会有一份计划消耗的卡路里表，其中 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 的长度。

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

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;
  }
}

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;
  }
};

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
}

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)$。

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

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;
  }
}

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;
  }
};

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
}

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;
}