题解 | #牛群放牧顺序#

牛群放牧顺序

https://www.nowcoder.com/practice/69f5f2d04d1c41df8d4e0691f6ef6935

考察的知识点:贪心;

解答方法分析:

  1. 定义了两个等长的数组 left 和 right,用来记录每个元素的左边和右边的最长递增子序列长度。
  2. 遍历数组 ratings,从前往后,如果当前元素大于前一个元素,则将左边的最长递增子序列长度加 1,否则不变。
  3. 遍历数组 ratings,从后往前,如果当前元素大于后一个元素,则将右边的最长递增子序列长度加 1,否则不变。
  4. 定义一个变量 totalPastureTime 来累加左右两边最长递增子序列的较大值。
  5. 返回 totalPastureTime,即为最小牧场时间。

所用编程语言:C++;

完整编程代码:↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param ratings int整型vector
     * @return int整型
     */
    int min_pasture_time(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i= n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int totalPastureTime = 0;
        for (int i = 0; i < n; i++) {
            totalPastureTime += max(left[i], right[i]);
        }
        return totalPastureTime;
    }
};

全部评论

相关推荐

机械打工仔:有说的你怀疑一下就行了,直接问也太实诚了
点赞 评论 收藏
分享
苍蓝星上艾露:这简历。。。可以试试我写的开源简历优化工具https://github.com/weicanie/prisma-ai
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务