代码随想录算法训练营第三十四天|LeetCode135 分发糖果

题1:

指路:135. 分发糖果 - 力扣(LeetCode)
思路与代码:

这个题我们需要分开情况考虑:右边的分数大于左边,这时候右边对应的糖果数量就要在左边的基础上加一;相似的,再考虑左边的分数大于右边,这时候需要从后往前遍历,此时左边对应的数量就要在右边的基础上加一。如此,我们会在一个孩子的对应糖果值上得到两个值,选取较大值可以满足这两个条件。最后将得到的糖果数量累加即可。代码如下:

class Solution {
public:
    int candy(vector<int>& ratings) {
    int ans = 0;
    int n = ratings.size();
    vector<int>candy (n, 1);  // n个1初始化糖果
    for (int i = 1; i < ratings.size(); i++) { 
        if (ratings[i] > ratings[i - 1]) {  // 右边大于左边
            candy[i] = candy[i - 1] + 1;
        }
    }
    for (int i = ratings.size() - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {  // 左边大于右边
            candy[i] = max(candy[i], candy[i + 1] + 1);
        }
    }
    for (int i = 0; i < candy.size(); i++) {
        ans += candy[i];
    }
    return ans;
    }
};

最近更新

  1. git配置2-不同的代码托管平台配置不同的ssh key

    2024-06-11 19:06:03       0 阅读
  2. web前端何去何从:探索未来之路

    2024-06-11 19:06:03       0 阅读
  3. web前端换行命令:深入解析与实用技巧

    2024-06-11 19:06:03       0 阅读
  4. react有什么特点

    2024-06-11 19:06:03       0 阅读
  5. Python内置函数pow()详解

    2024-06-11 19:06:03       0 阅读
  6. 【数据结构与算法】广度优先搜索(BFS)

    2024-06-11 19:06:03       0 阅读

热门阅读

  1. 使用redis构建简单的社交网站

    2024-06-11 19:06:03       3 阅读
  2. c语言之 **指针

    2024-06-11 19:06:03       3 阅读
  3. 008.googleNet-FashionMNIST-正确率90.510

    2024-06-11 19:06:03       3 阅读
  4. Android13 Settings 左上角箭头图标点击无效

    2024-06-11 19:06:03       3 阅读
  5. 【摘葡萄game】

    2024-06-11 19:06:03       4 阅读
  6. C++ Primer Chapter 8 The IO Library

    2024-06-11 19:06:03       3 阅读
  7. 深度学习的可微渲染

    2024-06-11 19:06:03       3 阅读
  8. Linux学习问题

    2024-06-11 19:06:03       2 阅读
  9. NAT

    NAT

    2024-06-11 19:06:03      4 阅读
  10. 享元模式

    2024-06-11 19:06:03       3 阅读
  11. css特效:对多个tag标签实现模拟地球仪特效

    2024-06-11 19:06:03       2 阅读