135. Candy

目录

题目描述

贪心

题目描述

135. Candy

贪心

考虑右边的比左边大的情况，必须从前到后遍历。

考虑左边的比右边大的情况，必须从后到前遍历。

先考虑哪种情况都可以。

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();int res = n;vector<int> candis(n,1);for(int i = 1;i < n;i++){//右边的比左边的大if(ratings[i] > ratings[i-1]){res += (candis[i-1] +1 -candis[i]);candis[i] = candis[i-1]+1;}}for(int i = n-2;i >=0;i--){//左边的比右边的大if(ratings[i] > ratings[i+1] && candis[i] <= candis[i+1]){res += (candis[i+1]+1-candis[i]);candis[i] = candis[i+1]+1;}}return res;}
};

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();int res = n;vector<int> candis(n,1);for(int i = n-2;i >=0;i--){//左边比右边大if(ratings[i] > ratings[i+1]){res+= (candis[i+1]+1-candis[i]);candis[i] = candis[i+1]+1;}}for(int i = 1;i < n;i++){//右边比左边大if(ratings[i] > ratings[i-1] && candis[i]<= candis[i-1]){res+= (candis[i-1]+1 - candis[i]);candis[i] = candis[i-1]+1;}}return res;}
};