题解 | #牛的生长情况#

知识点

单调栈

思路

我们可以使用一个单调栈维护weights数组的下标。遍历weights数组时，当weights[i]比栈的顶部对应的质量大时，更新答案数组ans[st.top()]=i-st.top()，并且将对应下标弹出栈。在栈顶下标对应的质量不大于当前weights[i]时，再将当前i入栈.

思路类似动态规划的最大上升子序列的单调栈优化

代码

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

    }
};