Posted on 2014-01-17 02:49
Uriel 阅读(147)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
N个人，每个人有个rating，开始分糖，若某个人rating大于其邻居，则拿的糖数也要比那个邻居多，每个人至少一颗糖，问至少要准备多少糖。
从头到尾，从尾到头扫两遍即可
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 };