Posted on 2014-01-17 02:49
Uriel 閱讀(181)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
LeetCode
N個(gè)人，每個(gè)人有個(gè)rating，開(kāi)始分糖，若某個(gè)人rating大于其鄰居，則拿的糖數(shù)也要比那個(gè)鄰居多，每個(gè)人至少一顆糖，問(wèn)至少要準(zhǔn)備多少糖。
從頭到尾，從尾到頭掃兩遍即可
1 class Solution {
2 public:
3 int candy(vector<int> &ratings) {
4 int tp = 1, res = ratings.size(), mi = 1;
5 int can[100010];
6 memset(can, 0, sizeof(can));
7 if(ratings.empty()) return 0;
8 for(int i = 1; i < ratings.size(); ++i) {
9 if(ratings[i] > ratings[i - 1]) {
10 can[i] = tp++;
11 }
12 else
13 tp = 1;
14 }
15 tp = 1;
16 for(int i = ratings.size() - 2; i >= 0; --i) {
17 if(ratings[i] > ratings[i + 1]) {
18 can[i] = max(tp++, can[i]);
19 }
20 else
21 tp = 1;
22 }
23 for(int i = 0; i < ratings.size(); ++i) res += can[i];
24 return res;
25 }
26 };