70年弹指一挥,新时代的中国,山河无恙,国富民强。祝大家国庆快乐!
Problem Statement
A dieter consumes calories[i]
calories on the i
-th day.
Given an integer k
, for every consecutive sequence of k
days (calories[i], calories[i+1], ..., calories[i+k-1]
for all 0 <= i <= n-k
), they look at T, the total calories consumed during that sequence of k
days (calories[i] + calories[i+1] + ... + calories[i+k-1]
):
T < lower
, they performed poorly on their diet and lose 1 point; T > upper
, they performed well on their diet and gain 1 point;Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length
days.
Note that the total points can be negative.
Example 1:
Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explanation: Since k = 1, we consider each element of the array separately and compare it to lower and upper.
calories[0] and calories[1] are less than lower so 2 points are lost.
calories[3] and calories[4] are greater than upper so 2 points are gained.
Example 2:
Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explanation: Since k = 2, we consider subarrays of length 2.
calories[0] + calories[1] > upper so 1 point is gained.
Example 3:
Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explanation:
calories[0] + calories[1] > upper so 1 point is gained.
lower <= calories[1] + calories[2] <= upper so no change in points.
calories[2] + calories[3] < lower so 1 point is lost.
Constraints:
1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper
Problem link
You can find the detailed video tutorial here
This is an easy problem but might be a bit hard to code it up correctly in one pass. We can use a sliding window to keep a rolling sum and compare it with upper and lower bound.
A few caveats in implementation:
1 public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
2 if (calories == null || calories.length == 0) {
3 return 0;
4 }
5
6 int rollingSum = 0;
7 int performance = 0;
8
9 for (int i = 0; i < calories.length; i++) {
10 // always adding element to the sliding window on the right
11 rollingSum += calories[i];
12 // initial value
13 if (i < k - 1) {
14 continue;
15 }
16
17 // when to pop out element on the left
18 if (i >= k) {
19 rollingSum -= calories[i - k];
20 }
21 if (rollingSum > upper) {
22 performance++;
23 }
24 if (rollingSum < lower) {
25 performance--;
26 }
27 }
28
29 return performance;
30 }
Time Complexity: O(N) visited the array once
Space Complexity: O(1) No extra space is needed