首页 > 代码库 > Leetcode:Candy 每个数都比相邻数大

Leetcode: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?

 

 

class Solution {public:    int candy(vector<int> &ratings) {        std::vector<int> num(ratings.size(), 1);                int inc = 2;        for (int i = 1; i < ratings.size(); ++i) {            if (ratings.at(i) > ratings.at(i - 1)) {                num.at(i) = std::max(inc++, num.at(i));            } else {                inc = 2;            }        }        inc = 2;        for (int i = ratings.size() - 2; i >= 0; --i) {            if (ratings.at(i) > ratings.at(i + 1)) {                num.at(i) = std::max(inc++, num.at(i));            } else {                inc = 2;            }        }        int res = std::accumulate(num.begin(), num.end(), 0);        return res;    }};

step1. 首先将辅助数组每个元素初始化为1,因为每个元素都至少为1

step2. 从左向右扫描,如果某个数比其左相邻数大,则num数组对应位置的这个数从2开始递增赋值 (注意相等是不需要增加的),否则递增量初始为2

         遍历完之后,可以满足:如果 原数组中某个数大于其左相邻数,那么对应辅助数组中也一定是大于其左相邻数

         如果 ratings[i] >= ratings[i+1] 此时ratings[i+1]一定为1

step3. 从右向左遍历,类似step2

 

其实step2中 num.at(i)一定是等于inc++的,因为num.at(i)未改变之前都是初始为1的

为什么step3中一定要加上 inc比num.at(i)的比较呢? 因为此时 必须满足step2之后数组的大小条件

原数组为:1 --> 2 --> 5 --> 4 --> 3 --> 2 --> 1step2之后 num数组为:1 --> 2 --> 3 --> 1 --> 1 --> 1 --> 1step3从右向左遍历到idx=2时 : 1 --> 2 --> (3 or 5)--> 4 --> 3 --> 2 --> 1

 

idx=2位置处,必须满足它比左相邻数大,比右相邻数大,所以才有了max操作

Leetcode:Candy 每个数都比相邻数大