下一个更大元素 IV

下一个更大元素 IV

//双单调栈,满足条件进第二个
class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        // 定义两个单调栈
        // 主栈
        Deque<Integer> stack1 = new ArrayDeque<>();  
         // 辅助栈
        Deque<Integer> stack2 = new ArrayDeque<>(); 
        for (int i = 0; i < n; i++) {
            int current = nums[i];
            // 处理辅助栈中可以被当前元素更新的元素
            while (!stack2.isEmpty() && nums[stack2.peek()] < current) {
                int index = stack2.pop();
                res[index] = current;
            }
            // 从主栈中找到需要移动到辅助栈的元素
            Deque<Integer> temp = new ArrayDeque<>();
            while (!stack1.isEmpty() && nums[stack1.peek()] < current) {
                temp.push(stack1.pop());
            }
            // 将需要移动的元素从临时栈转移到辅助栈
            while (!temp.isEmpty()) {
                stack2.push(temp.pop());
            }
            // 当前索引入主栈
            stack1.push(i);
        }
        
        return res;
    }
}