Leetcode 135.分发糖果

mac2025-02-10  14

文章目录

问题描述问题解析代码实现

问题描述

问题解析

前向遍历糖果数组,则相邻的孩子中,分高且位于后面的孩子必定能分到较多的糖果; 后向遍历糖果数组,则相邻的孩子中,分高且位于前面的孩子必定能分到较多的糖果。

代码实现

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