题解 | #牛的生长情况#

知识点

双端队列，单调维护

解题思路

某个元素B要成为之前元素A的首个大于的数，条件就需要在元素B之前没有比他大的数来阻止他成为A首个大的数。

因此我们可以从后往前遍历数组，维护一个存放元素下标的双端队列，当遍历到的这个元素大于队列中的元素，相当于当前元素就能阻挡后面比他小的元素，所以需要剔除队列中比他小的元素，这样下来对列中的元素就是单调递增的，而ans[i]就是对列中下一个元素 - 当前i。如果队列中此时没有元素，说明后面没有比当前元素大的的了。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型一维数组 
     * @return int整型一维数组
     */
    public int[] weightGrowth (int[] weights) {
        // write code here
        Deque<Integer> deque = new LinkedList<>();
        int n = weights.length;
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; i--){
            while(!deque.isEmpty() && weights[i] >= weights[deque.getFirst()]){
                deque.pollFirst();
            }
            if(deque.isEmpty()){
                ans[i] = -1;
            } else {
                ans[i] = deque.getFirst() - i;
            }
            deque.offerFirst(i);
        }
        return ans;
    }
}