思路分析
这种类型的DP或者说贪心问题，我现在还是比较无能为力的，可能还是需要参考别人思路才能做出来，功底还是不够啊。其实这题基于的核心思想还是“双端扫描”，但这里面所包含的贪心成分更多一些。
首先我们考虑，如果尝试只满足左边，那么显然从左往右扫描一遍，每次遇到升序就增加发放的糖果数量，否则就只发一个糖果即可。这样得到的糖果发放序列，即为满足“大于左侧邻居”的序列。同样的道理，如果我们从右往左扫描并这样维护，得到的是满足“大于右侧邻居”的序列。最后我们遍历一遍这两个等长序列，取每个位置的最大值，显然就是既满足左侧又满足右侧条件的序列，将其求和即为答案。
代码
class Solution {
public:
int candy(vector<int> &ratings) {
if ( ratings.size() < 2 ) return 1;
int *left = new int[ratings.size()], *right = new int[ratings.size()];
left[0] = 1;
for ( int i = 1; i < ratings.size(); i++ ) {
if ( ratings[i] > ratings[i - 1] ) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
right[ratings.size() - 1] = 1;
for ( int i = ratings.size() - 2; i >= 0; i-- ) {
if ( ratings[i] > ratings[i + 1] ) {
right[i] = right[i + 1] + 1;
} else {
right[i] = 1;
}
}
int res = 0;
for ( int i = 0; i < ratings.size(); i++ ) res += max(left[i], right[i]);
return res;
}
};