# 2454. Next Greater Element IV
###### tags: `Leetcode` `Hard` `Monotonic Stack`
Link: https://leetcode.com/problems/next-greater-element-iv/description/
## 思路
### Two Monotonic Stacks
思路[参考](https://leetcode.com/problems/next-greater-element-iv/solutions/2756668/java-c-python-one-pass-stack-solution-o-n/)
我们可以用一个单调栈解决next greater的问题
那么如果解决第二个next greater的问题呢
答案就是用两个栈

我们遍历```nums``` 对于每一个```num```
我们先pop掉所有在```s2```的top并且小于```num```的数字 因为```num```已经是他们的second greater element
然后我们pop掉所有在```s1```的top并且小于```num```的数字放在```temp```里面 他们已经找到了first greater element 这里注意temp里面的element是non-decreasing顺序
我们再把这些pop掉的数字放进```s2```

这时候可能有个问题是我们现在保证了所有刚从```s1``` pop出来的element都是non-increasing order 但是如果保证把这些element塞进```s2```之后 ```s2```还是non-increasing的
也就是有没有可能```s2```之前有一个element比新从```s1``` pop出来的element小
例如之前```s2```是```[6,5,4]``` ```s1``` pop出来的element是```[5,4,3]```
答案是不可能的 因为如果这个5在```s1```里面 那说明它的index比```s2```的最后一个4在```nums```里的index大 也就是这个5是后面才出现的 那么```s2```里面的最后一个4肯定会在5出现的时候被pop出去 所以这种情况是不可能出现的
### Monotonic Stack + Priority Queue
参考[这里](https://leetcode.com/problems/next-greater-element-iv/solutions/2756341/c-java-python3-monotonic-stack-priority-queue/)
先记录每个数字是谁的next greater element
然后再遍历一遍所有nums 对于每一个num 找到priority Queue里面所有比它小的element 它们的second greater element就是num 然后再把当前element的prev smaller element放进去
对于每一个放入priority queue的element来说 我们已经找到了他们的next greater element 所以我们接下来要做的就是找到除了next greater element的下一个element
## Code
### Monotonic Stack

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        //non-increasing stack
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        Stack<Integer> temp = new Stack<>();
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
        for(int i=0; i<nums.length; i++){
            while(!s2.isEmpty() && nums[s2.peek()]<nums[i]){
                ans[s2.pop()] = nums[i];
            }
            while(!s1.isEmpty() && nums[s1.peek()]<nums[i]){
                temp.add(s1.pop());
            }
            while(!temp.isEmpty()){
                s2.add(temp.pop());
            }
            s1.push(i);
        }
        return ans;
    }
}

### Monotonic Stack + Priority Queue

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        List<List<Integer>> next = new ArrayList<>();
        int n = nums.length;
        for(int i=0; i<n; i++) next.add(new ArrayList<>());
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<n; i++){
            while(!stack.isEmpty() && nums[stack.peek()]<nums[i]){
                next.get(i).add(stack.pop());
            }
            stack.push(i);
        }
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Queue<Integer> pq = new PriorityQueue<>((a,b)->(nums[a]-nums[b]));
        for(int i=0; i<n; i++){
            while(!pq.isEmpty() && nums[pq.peek()]<nums[i]){
                ans[pq.poll()] = nums[i];
            }
            for(int j:next.get(i)){
                pq.add(j);
            }
        }
        return ans;
    }
}