题解 | 牛的生长情况

语言： C++

知识点： 单调栈

分析： 本题要求之后第一个比当前数大的数的位置，因此可以维护一个单调递减的栈，又因为最终返回的是数字之间的距离，因此栈中存储的应该是当前体重的下标（注意此处的单调递减是指栈中下标所对应的体重值单调递减，而非栈中下标值单调递减）。之后在遍历过程中若遇到当前体重大于栈顶下标所对应的体重时，则当前下标减去栈顶下标即为栈顶下标处的结果（栈顶下标处体重到下一个大于它的体重的距离），然后将栈顶弹出继续和新的栈顶比较，直到满足该元素入栈后栈中可以单调递减为止。最终遍历完成即可返回结果集（注意题目要求后面找不到大于的要返回-1，因此结果集要初始化为-1）。

代码实现：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @return int整型vector
     */
    vector<int> weightGrowth(vector<int>& weights) {
        stack<int> sk;
        vector<int> res(weights.size(), -1); // 结果集初始化为-1
        for(int i = 0; i < weights.size(); i++)
        {
            while(!sk.empty() && weights[i] > weights[sk.top()])
            {
                res[sk.top()] = i - sk.top();
                sk.pop();
            }
            sk.push(i);
        }
        return res;
    }
};