题解 | #牛群放牧顺序#

考察的知识点：贪心；

解答方法分析：

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