牛客題霸 [分糖果問題] C++題解/答案

題目描述

一群孩子做游戲，現在請你根據游戲得分來發糖果，要求如下：

每個孩子不管得分多少，起碼分到一個糖果。

任意兩個相鄰的孩子之間，得分較多的孩子必須拿多一些糖果。(若相同則無此限制)
給定一個數組arr代表得分數組，請返回最少需要多少糖果。
[要求]
時間復雜度為On, 空間復雜度為O1

題解：

正著來一遍，倒著來一遍
根據大小關系遞歸賦值

代碼：

class Solution { public:/*** pick candy* @param arr int整型vector the array* @return int整型*/int candy(vector<int>& arr) {// write code hereint len=arr.size();int sum=0;vector<int>a(len,1);for(int i=1;i<len;i++){if(arr[i]>arr[i-1])a[i]=a[i-1]+1;}for(int i=len-2;i>=0;i--){if(arr[i]>arr[i+1])a[i]=max(a[i],a[i+1]+1);}for(int i=0;i<len;i++)sum+=a[i];return sum;} };

總結

以上是生活随笔為你收集整理的牛客题霸 [分糖果问题] C++题解/答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。