题解 | #牛群放牧顺序#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

贪心算法

题目解答方法的文字分析

这道题目可以使用贪心算法来解决。我们可以通过从左到右和从右到左两次遍历数组，分别计算每头牛左边和右边比其优先级高的牛的数量。

具体步骤如下：

1. 初始化两个数组left和right，分别表示每头牛左边和右边比其优先级高的牛的数量，数组元素全部初始化为1。
2. 从左到右遍历数组ratings，更新left数组的值，如果当前牛的优先级比前一头牛高，则更新left[i] = left[i-1] + 1。
3. 从右到左遍历数组ratings，更新right数组的值，如果当前牛的优先级比后一头牛高，则更新right[i] = right[i+1] + 1。
4. 最终，每头牛的放牧次数为max(left[i], right[i])，将所有牛的放牧次数累加得到最终的最小放牧次数。

本题解析所用的编程语言

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);

        // 从左到右更新left数组
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }

        // 从右到左更新right数组
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }

        int minPastureTime = 0;
        for (int i = 0; i < n; ++i) {
            minPastureTime += max(left[i], right[i]);
        }

        return minPastureTime;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！