Java solution using two Stacks O(n)
IntuitionApproachUse two stack s1 and s2.
Similar to "Next Greater Element"
s1 stores the index of elements
that have not found their first greater element.s2 s
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
Use two stack s1 and s2.
Similar to "Next Greater Element"
s1 stores the index of elements
that have not found their first greater element.

s2 stores the index of elements
that have found their first greater element,
have not found their second greater element.

For each a = A[i] in A
We first compare the a with the tail elements in s2,
pop all element smaller than a,
because a is their second greater element.

Then we compare the a with the tail elements in s1,
move all elements smaller than a to the tail of s2,
because a is their first greater element.

We repeatly do this for all A[i] and finally return the result.

<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] nextGreater = new int[n];
        
        Arrays.fill(nextGreater,-1);
        Stack<Integer> s1 = new Stack<>(),s2 = new Stack<>(),temp = new Stack<>();

        for(int i=0; i<n ;i++){
            while(!s2.isEmpty() && nums[s2.peek()] < nums[i]){
                nextGreater[s2.pop()] = nums[i];
            }
            while(!s1.isEmpty() && nums[s1.peek()] < nums[i]){
                temp.push(s1.pop());
            }
            while(!temp.isEmpty()){
                s2.push(temp.pop());
            }
            s1.push(i);

           
        }
        
        return nextGreater;
    }
}
```
['Array', 'Stack', 'Java']