算法分析与设计►贪婪算法

candies

  • 问题来源
  • 问题简介
    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?

解题思路


不同速度的人站在一起，根据速度画成图的话，要不就是一条直线，要不就是逐渐变高，要不就是逐渐变低。则：
一条直线的话：
除第一个外，其他所有人都可以只给1个糖果
上升：
每一个人获得的糖果都必须比前一个多1
下降:
每一个人获得的糖果都必须比前一个少1

时间复杂度 空间复杂度
O(未知) O(未知)

Code

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> nums(ratings.size(), 1);
        int sum = 0, i = 0, len = ratings.size();
        int upCount = 0, downCount = 0;
        while (i < len - 1) {
            upCount = downCount = 0;
            if (i < len - 1 && ratings[i] == ratings[i+1]) {
                while (i < len - 1 && ratings[i] == ratings[i+1]) { i++; }
            }
            int start = i;
            while (i < len - 1 && ratings[i] < ratings[i+1]) {
                upCount++;
                nums[i+1] = nums[i] + 1;
                i++;
            }
            int top = i;
            while (i < len - 1 && ratings[i] > ratings[i+1]) {
                downCount++;
                i++;
            }
            for (int j = i - 1; j > top; j--) {
                nums[j] = nums[j+1] + 1;
            }
            if (downCount > upCount) {
                nums[top] += downCount - upCount;
            }
        }
        for (auto num : nums) {
            sum += num;
        }
        return sum;
    }
};

运行结果

candies