题解 | #牛的生长情况#

• 题目考察的知识点 : 单调栈
• 题目解答方法的文字分析：

1. 可以维护一个单调不升的栈stk，其中栈顶元素对应的体重最小、离当前位置最近的牛。从右往左遍历整个数组：
2. 如果当前牛的体重大于等于栈顶元素的体重，则将栈顶元素出栈，并修改其下一个平均体重更高的天数为当前天数减去其下标；
3. 重复步骤 2 直到栈为空或者当前牛的体重小于栈顶元素的体重；
4. 将当前牛的下标入栈。

在上述过程中，若栈不为空，则栈顶元素的下一个平均体重更高的天数为 -1

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param weights int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def weightGrowth(self , weights: List[int]) -> List[int]:
        n = len(weights)
        stk = []
        res = [-1] * n

        for i in range(n - 1, -1, -1):
            while stk and weights[i] >= weights[stk[-1]]:
                stk.pop()
            if stk:
                res[i] = stk[-1] - i
            stk.append(i)

        return res