下一个更大元素 II

下一个更大元素 II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res,-1);
        //定义单调栈
        Deque<Integer> stack  = new ArrayDeque<>();
        //从0开始
        for(int i = 0;i <  nums.length;i++){
            //找到会更新单调栈
            while(!stack.isEmpty()&&nums[stack.peek()] < nums[i]){
                int index = stack.pop();
                res[index] = nums[i];
            }
            //之后往栈加入自己
            stack.push(i);
        }
        //遍历一遍之后,从头开始寻找未找到的
        while(!stack.isEmpty()){
            int index  = stack.pop();
            for(int i = 0;i < index;i++){
                if(nums[i] > nums[index]){
                    res[index] = nums[i];
                    break;
                }
            }
        }

        return res;
    }
}