题解 | #牛的生长情况#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @return int整型一维数组
     */
    public int[] weightGrowth (int[] weights) {
        // write code here
        // 单调栈
        if (weights == null || weights.length < 1) return new int[] {};
        int[] res = new int[weights.length];
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        for (int i = 1; i < weights.length; i++) {
                if (weights[i] > weights[stack.peek()]) {
                    // 当栈顶元素小于遍历到的i位置元素时
                    while (!stack.isEmpty() && weights[i] > weights[stack.peek()]) {
                        int tmp = stack.pop();
                        res[tmp] = i - tmp;
                    }
                    stack.push(i);
                } else{
                    stack.push(i);
                }
        }
        // 结算阶段
        while (!stack.isEmpty()) {
            res[stack.pop()] = -1;
        }
        return res;
    }
}

题目描述：在一个牧场中，有n头牛，每头牛的体重都在增长。给定一个整数数组weights，表示每天的牛的平均体重，返回一个数组growth，其中growth[i]是指对于第i天，下一个平均体重更高的是在几天后。如果在这之后平均体重都不会增长，请在该位置用-1来代替。

思路：这个题目要求的求解数组中每一个元素右边最近且比它大的值离它多远。

我们做一个从下到上单调递减的栈结构，从左到右遍历数组，当数组中遍历到的元素大于栈顶元素的时候，将栈顶元素依次弹出直到栈顶元素比它大为止，然后将数组元素下标放到栈中，继续下一个数组元素，并且弹出的栈顶元素最右边离他最近且比它大的元素就是数组中本次遍历到的元素，通过下标计算就可以得出距离是多少。当栈顶元素不小于数组中遍历的元素时，就直接将这个元素压入栈中。

最后，当遍历完数组后，如果栈中还有元素，说明栈中的元素在数组中右边没有比他大的元素，依次弹出栈中元素，直接赋值-1即可.

为什么做一个从下到上单调递减的栈结构？

栈中从下到上单调递减对应数组中从左到右遍历单调递减，要找到右边离他最近且比他大的元素，则比他小的元素对它本身没有任何影响，且比他小的元素也要处理，而且如果比栈底元素要大，肯定比栈顶元素大；比栈顶元素大，不一定比栈底元素大；所以取从下到上单调递减的结构