题解 | #牛群放牧顺序# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param ratings int整型一维数组
     * @return int整型
     */
    public int min_pasture_time (int[] ratings) {
        // write code here
        int n = ratings.length;
        if (n == 0) {
            return 0;
        }

        int[] leftToRight = new int[n]; // 从左到右，保存每头牛放牧次数
        int[] rightToLeft = new int[n]; // 从右到左，保存每头牛放牧次数

        // 从左到右遍历，如果优先级较高的牛放牧次数少于右边的牛，则设置放牧次数为右边牛放牧次数+1
        leftToRight[0] = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                leftToRight[i] = leftToRight[i - 1] + 1;
            } else {
                leftToRight[i] = 1;
            }
        }

        // 从右到左遍历，如果优先级较高的牛放牧次数少于左边的牛，则设置放牧次数为左边牛放牧次数+1
        rightToLeft[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                rightToLeft[i] = rightToLeft[i + 1] + 1;
            } else {
                rightToLeft[i] = 1;
            }
        }

        // 对于每头牛，取左右放牧次数的最大值，保证优先级高的牛放牧次数更多
        int totalMinTime = 0;
        for (int i = 0; i < n; i++) {
            totalMinTime += Math.max(leftToRight[i], rightToLeft[i]);
        }

        return totalMinTime;
    }
}

编程语言是Java。

这道题考察的主要知识点包括：

1. 数组的遍历与操作
2. 动态规划：通过动态规划的思想，分别从左到右和从右到左计算每头牛的放牧次数。

以下是代码的解释：

• min_pasture_time 方法接受一个整数数组 ratings 作为参数，表示每头牛的优先级值。
• 创建两个数组 leftToRight 和 rightToLeft，分别用于从左到右和从右到左保存每头牛的放牧次数。
• 从左到右遍历 ratings 数组，比较当前牛和前一头牛的优先级。如果当前牛的优先级较高，则放牧次数为前一头牛的放牧次数加1，否则为1。
• 从右到左遍历 ratings 数组，比较当前牛和后一头牛的优先级。如果当前牛的优先级较高，则放牧次数为后一头牛的放牧次数加1，否则为1。
• 遍历每头牛，对于每头牛，选择左右放牧次数的最大值，保证优先级较高的牛放牧次数更多。
• 返回总的最少放牧次数，即 totalMinTime。