首页 > 代码库 > [LeetCode] Candy

[LeetCode] Candy

2024-07-09 13:45:46   217人阅读

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?

例子：

input ： 　　　  1 1 7 6 5 9 7

第一次扫描：　　1 1 2 1 1 2 1

第二次扫描：　　1 1  3  2  1 2 1

 1 class Solution { 2 public: 3     int candy(vector<int> &ratings) { 4         int res = 0; 5         int n = ratings.size(); 6         if (n == 0) { 7             return res; 8         } 9         int *t = new int[n];10         for (int i = 0; i < n; ++i) {11             t[i] = 1;12         }13         //从左向右扫描  ，保证当前比前一个多14         for (int i = 1; i < n; ++i) {15             if (ratings[i] > ratings[i-1]) {16                 t[i] = t[i-1] + 1;17             }18         }19         //从右向左扫描， 保证当前比后一个多     20         for(int i = n-2;i >= 0;i--)21         {             22             //如果第i个的小孩的权值比i+1个小孩高,但是糖的数目却小或者相等，那么i的糖数目等于i+1的糖数目+1。             23             if(ratings[i] > ratings[i+1] && t[i] <= t[i+1])24             {                 25                 t[i] = t[i+1] + 1;            26             }      27         }28         for (int i = 0; i < n; ++i) {29             res += t[i];30         }31         return res;32     }33 };

 


联系
我们