题解 | #牛的生长情况#

考察知识点：数组、单调栈

题目分析：

方法一：双指针

遍历一遍数组即可。指针i指向第i天，用指针j向后查找看那一天能大于第i天的体重，返回j与i的差值即可。没有找到则返回-1。

方法二：单调栈

单调栈适合解决这种找与某个数最近的更大的数或更小的数的问题。

如果我们想要找到右边序列中更大或更小的数，那么就是说我需要先知道右边的数，即我需要从右向左遍历。

如上图所示，第一个遍历到的数是13，他右边没有数，所以它对应的grouth就是-1。而第二个遍历到的数是76，右边的数是13比他小，所以它对应的grouth是-1。第三个数是72，右边的数是76和13，此时发现左边数的grouth不可能取到13了，因为76比13要大，76总是先被取到。

也就是说，如果将所有遍历到的数放入栈中，如果指针i指向的数比栈顶大，那么就不断将栈顶删除，直到找到栈中的数比指针i要大即可：

上图中，71能很快找到右边比他大的最近的数是72，75右边比它大的数是76。

注意栈中应该存放每个数的坐标，方便计算天数之差。

所用编程语言：C++

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

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