135.Candy

135. Candy

题目地址

https://leetcode.com/problems/candy/

题目描述

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

Example 1:
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.

代码

Approach #2 Using two arrays

Complexity Analysis

• Time complexity : O(n)

• Space complexity : O(n)

class Solution {
  public int candy(int[] ratings) {
    int sum = 0;
    int[] left2right = new int[ratings.length];
    int[] right2left = new int[ratings.length];
    Arrays.fill(left2right, 1);
    Arrays.fill(right2left, 1);
    for (int i = 1; i < ratings.length; i++) {
      if (ratings[i] > ratings[i - 1]) { // 右边大
        left2right[i] = left2right[i - 1] + 1;
      }
    }
    for (int i = ratings.length - 2; i >= 0; i--) {
      if (ratings[i] > ratings[i + 1]) { // 左边大
        right2left[i] = right2left[i + 1] + 1；
      }
    }

    for (int i = 0; i < ratings.length; i++) {
      sum += Math.max(left2right[i], right2left[i]);
    }

    return sum;
  }
}

Approach #3 Using one array

class Solution {
  public int candy(int[] ratings) {
    int[] candies = new int[ratings.length];
    Arrays.fill(candies, 1);
    for (int i = 1; i < ratings.length; i++) {
      if (ratings[i] > ratings[i - 1]) {
        candies[i] = candies[i - 1] + 1;
      }
    }
    int sum  = candies[ratings.length - 1];
    for (int i = ratings.length - 2; i >= 0; i--) {
      if (ratings[i] > ratings[i + 1]) {
        candies[i] = Math.max(candies[i], candies[i + 1] + 1);
      }
      sum += candies[i];
    }

    return sum;
  }
}

Approach 1: Brute Force

Complexity Analysis

• Time complexity : O(n^2). We need to traverse the array at most n times.

• Space complexity : O(n). One candies array of size n is used.

class Solution {
  public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
    Arrays.fill(candies, 1);
    boolean flag = true;
    int sum = 0;
    while (flag) {
      for (int i = 0; i < ratings.length; i++) {
        if ( i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
          candies[i] = candies[i + 1] + 1;
          flag = true;
        }

        if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] < candies[i - 1]) {
          candies[i] = candies[i - 1] + 1;
          flag = true;
        }
      }
    }

    for (int candy : candies) {
      sum += candy;
    }
    return sum;
  }
}

Approach #4 Single Pass with Constant Space Confused

public class Solution {
    public int count(int n) {
        return (n * (n + 1)) / 2;
    }
    public int candy(int[] ratings) {
        if (ratings.length <= 1) {
            return ratings.length;
        }
        int candies = 0;
        int up = 0;
        int down = 0;
        int old_slope = 0;
        for (int i = 1; i < ratings.length; i++) {
            int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
            if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) {
                candies += count(up) + count(down) + Math.max(up, down);
                up = 0;
                down = 0;
            }
            if (new_slope > 0)
                up++;
            if (new_slope < 0)
                down++;
            if (new_slope == 0)
                candies++;

            old_slope = new_slope;
        }
        candies += count(up) + count(down) + Math.max(up, down) + 1;
        return candies;
    }
}