两次遍历
- 思路:
- 先从前往后遍历一次数组,如果后比前大,后获得的糖果数比前的加1,否则发1块糖果;
- 然后从前往后遍历一次数组,如果后比前大,后获得糖果比前的加1,但是当前位置上同时要满足第一个规则,所以取两个规则中大的糖果数据;
class Solution {
public:
int candy(vector<int>& ratings) {
int size = ratings.size();
std::vector<int> left(size);
for (int i = 0; i < size; ++i) {
if (i > 0 && ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
int right = 0;
int result = 0;
for (int i = size - 1; i >= 0; i--) {
if (i < size - 1 && ratings[i] > ratings[i + 1]) {
right++;
} else {
right = 1;
}
result += std::max(left[i], right);
}
return result;
}
};