题解 | #牛群放牧顺序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param ratings int整型一维数组
     * @return int整型
     */
    public static 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;
    }
}

本题考察的知识点是栈的应用，所用编程语言是java。

我们先建立一个栈，目的建立一个一次递减序列，只要当前数组值小于栈顶元素时，就将其加入栈中。否则弹出栈顶元素。

弹出时需要判断此时栈中有多少个元素

如果此时栈中元素只有一个，需要判断此时栈顶元素对应的数组值与前一个下标值对应的数组值是否相等，如果相等，则总放牧次数加一，如果不相等，栈中元素依次弹出，则总放牧次数依次加1，加2，加3

等数组元素遍历结束后最后再判断栈中元素个数，如果此时栈中元素只有一个，需要判断此时栈顶元素对应的数组值与前一个下标值对应的数组值是否相等，如果相等，则总放牧次数加一，如果不相等，栈中元素依次弹出，则总放牧次数依次加1，加2，加3