题解 | #牛群放牧顺序#

题目考察的知识点是：

贪心算法。

题目解答方法的文字分析：

我们可以通过从左到右和从右到左两次遍历数组，分别计算每头牛左边和右边比其优先级高的牛的数量。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param ratings int整型一维数组
     * @return int整型
     */
    public int min_pasture_time (int[] ratings) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[ratings.length];
        int total = 0;
        for (int i = 0; i < ratings.length; i++) {
            if (stack.size() == 0) {
                stack.add(i);
            } else if (ratings[i] < ratings[stack.peek()]) {
                stack.add(i);
            } else {
                if (stack.size() == 1) {
                    int value = 1;
                    if (stack.peek() != 0 && ratings[stack.peek()] != ratings[stack.peek() - 1]) {
                        value = arr[stack.peek() - 1] + 1;
                    }
                    arr[stack.peek()] = value;
                    total += value;
                    stack.pop();
                } else {
                    int index = 1;
                    while (!stack.isEmpty()) {
                        arr[stack.peek()] = index;
                        total += arr[stack.peek()];
                        index++;
                        stack.pop();
                    }
                }
                stack.add(i);
            }
        }
        if (stack.size() == 1) {
            int value = 1;
            if (stack.peek() != 0 && ratings[stack.peek()] != ratings[stack.peek() - 1]) {
                value = arr[stack.peek() - 1] + 1;
            }
            total += value;
            stack.pop();
        } else {
            int index = 1;
            while (!stack.isEmpty()) {
                arr[stack.peek()] = index;
                total += arr[stack.peek()];
                index++;
                stack.pop();
            }
        }
        return total;
    }
}