题解 | #牛群放牧顺序#

• 题目考察的知识点 : 贪心算法
• 题目解答方法的文字分析：

1. 先将所有的牛按照优先级从小到大排序，然后从前往后遍历数组，并维护一个数组 count，其中 count[i] 表示第 i 头牛需要放牧的最少次数。
2. 对于当前遍历到的牛 i，如果该牛的优先级比前一头牛 j 的优先级高，则该牛需要放牧的次数应该比前一头牛多 1 次，即 count[i] = count[j] + 1。否则，该牛需要放牧的次数应该为 1，即 count[i] = 1。
3. 遍历完成后，返回 count 数组中所有元素的和即可

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param ratings int整型一维数组 
# @return int整型
#
class Solution:
    def min_pasture_time(self , ratings: List[int]) -> int:
        n = len(ratings)
        count = [1] * n # 每头牛至少需要放牧一次
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                count[i] = count[i-1] + 1
        for i in range(n-2, -1, -1): # 从后往前遍历
            if ratings[i] > ratings[i+1] and count[i] <= count[i+1]:
                count[i] = count[i+1] + 1
        return sum(count)