美文网首页
[Leetcode] 113. Candy

[Leetcode] 113. Candy

作者: 时光杂货店 | 来源:发表于2017-03-31 15:16 被阅读8次

    题目

    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?

    解题之法

    class Solution {
    public:
        int candy(vector<int>& ratings) {
            int res = 0;
            vector<int> num(ratings.size(), 1);
            for (int i = 0; i < (int)ratings.size() - 1; ++i) {
                if (ratings[i + 1] > ratings[i]) num[i + 1] = num[i] + 1;
            }
            for (int i = (int)ratings.size() - 1; i > 0; --i) {
                if (ratings[i - 1] > ratings[i]) num[i - 1] = max(num[i] + 1, num[i - 1]);
            }
            for (int i = 0; i < num.size(); ++i) {
                res += num[i];
            }
            return res;
        }
    };
    

    分析

    这道题看起来很难,其实解法并没有那么复杂。
    首先初始化每个人一个糖果,然后这个算法需要遍历两遍,第一遍从左向右遍历,如果右边的小盆友的等级高,等加一个糖果,这样保证了一个方向上高等级的糖果多。
    然后再从右向左遍历一遍,如果相邻两个左边的等级高,而左边的糖果又少的话,则左边糖果数为右边糖果数加一。
    最后再把所有小盆友的糖果数都加起来返回即可。

    相关文章

      网友评论

          本文标题:[Leetcode] 113. Candy

          本文链接:https://www.haomeiwen.com/subject/dubpottx.html