leetcode Question: Candy

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?

Analysis:

Scan the rating array from left to right and then from right to left. In every scan just consider the rising order (l->r: r[i]>r[i-1] or r->l: r[i]>r[i+1]), assign +1 candies to the rising position.
The final candy array is the maximum (max(right[i],left[i])) in each position.
The total candies is the sum of the final candy array.

The time complexity is O(n).

Code:


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

1 comment:


  1. Hello, Neat post. There is an issue scr888 apk download laptop together with your site in web explorer, may test this? IE nonetheless is the marketplace chief and a good component to people will omit your excellent writing because of this problem. The Gaming Club bears a license from the direction of Gibraltar, and claims to be one of a pick few casinos that have a license from the Gibraltar government. A enthusiast of the Interactive Gaming Council (IGC), The Gaming Club follows every the guidelines laid next to by the organization, something that has when a long mannerism in it instinctive qualified as a great area to gamble online.

    Everything practically The Gaming Club feels good; be it the promotions, the huge number of games, the combined banking options upon offer, the innovative security measures, or the fair and answerable gaming practices the casino adopts.

    The Gaming Club motors along on software developed by one of the giants of online gaming software go ahead Microgaming. The software it uses is enlightened and has a range of features meant to add up your online gambling experience and create you want to come encourage after every circular of gambling you get here.

    Another hallmark of a good casino is the air of its customer keep team, and The Gaming Club does not disappoint upon this front.
    https://onegold88.com/

    ReplyDelete