456 132 Pattern

class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums == null || nums.length == 0) return false;

        int n = nums.length;
        int[] mins = new int[n];
        mins[0] = nums[0];

        for (int i = 1; i < n; i++){
            mins[i] = Math.min(mins[i - 1], nums[i]);
        }

        Stack<Integer> stack = new Stack<>();
        for (int j = n - 1; j >= 0; j--){

            if (mins[j] < nums[j]){
                while (!stack.isEmpty() && stack.peek() <= mins[j]) stack.pop();

                if (!stack.isEmpty() && stack.peek() < nums[j]) return true;

                stack.push(nums[j]);    
            }

        }

        return false;
    }
}

496 Next Greater Element I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> hash = new HashMap<>();

        for (int i = 0; i < nums2.length; i++){
            int num2 = nums2[i];
            while (!stack.isEmpty() && num2 > stack.peek()){
                int cur = stack.pop();
                hash.put(cur, num2);
            }
            stack.push(num2);
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++){
            int num1 = nums1[i];
            int index = -1;
            if (hash.containsKey(num1)) index = hash.get(num1);
            ans[i] = index;
        }

        return ans;
    }
}

503 Next Greater Element II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();

        for (int i = nums.length - 1; i >= 0; i--){
            stack.push(nums[i]);
        }

        int[] ans = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--){
            ans[i] = -1;
            while (!stack.isEmpty() && stack.peek() <= nums[i]){
                stack.pop();
            }

            if (!stack.isEmpty()){
                ans[i] = stack.peek();
            }
            stack.push(nums[i]);
        }

        return ans;
    }
}