西安网站优化维护,摄影师网站,用html做网站搜索框,广州seo网站排名文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;本题的思路是要相比较一边#xff0c;然后在比较另外一边#xff0c;左右两边一起比较的代码非常难写… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析本题的思路是要相比较一边然后在比较另外一边左右两边一起比较的代码非常难写。每个孩子的糖果数量初始化为1。程序当中我们首先从前往后遍历若第i个孩子评分大于第i-1个孩子其糖果数量为第i-1个孩子的糖果数量1。然后从后往前遍历若第i个孩子比第i-1个孩子和第i1个孩子评分都高则要拿到比傍边孩子更多的糖果只需要在先前的candyVec[i]先前的candyVec[i]数量必然大于第i-1个孩子的糖果数量和第i1个孩子糖果数量1之间取最大值。 程序如下
class Solution {
public:int candy(vectorint ratings) {vectorint candyVec(ratings.size(), 1);for (int i 1; i ratings.size(); i) { // 从前往后遍历if (ratings[i] ratings[i - 1]) candyVec[i] candyVec[i - 1] 1; // 保证右边评分更大的孩子得到的糖果比左边多一颗}for (int i ratings.size() - 2; i 0; i--) { // 从后往前遍历if (ratings[i] ratings[i 1]) {candyVec[i] max(candyVec[i], candyVec[i 1] 1); // 保证左边更大的孩子得到的糖果比左边和右边都多取最大值}}return accumulate(candyVec.begin(), candyVec.end(), 0);}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include vector
# include algorithm
# include numeric
using namespace std;class Solution {
public:int candy(vectorint ratings) {vectorint candyVec(ratings.size(), 1);for (int i 1; i ratings.size(); i) { // 从前往后遍历if (ratings[i] ratings[i - 1]) candyVec[i] candyVec[i - 1] 1; // 保证右边评分更大的孩子得到的糖果比左边多一颗}for (int i ratings.size() - 2; i 0; i--) { // 从后往前遍历if (ratings[i] ratings[i 1]) {candyVec[i] max(candyVec[i], candyVec[i 1] 1); // 保证左边更大的孩子得到的糖果比左边和右边都多取最大值}}return accumulate(candyVec.begin(), candyVec.end(), 0);}
};int main() {vectorint ratings { 1,2,2 }; // 加油站的油量Solution s1;int result s1.candy(ratings);cout result endl;system(pause);return 0;
}end
