LeetCode 496. Next Greater Element I

Problem

LeetCode 496. Next Greater Element I

1. 题目简述

给出两个无重复数组nums1和nums2，nums1是nums2的子集，找出nums1中所有元素在nums2中的下一个更大的元素，如果没有，则为-1。例如：

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

2. 算法思路

相关问题：

1. LeetCode 503. Next Greater Element II
2. LeetCode 556. Next Greater Element III
3. LeetCode 739. Daily Temperatures(无解析)

monotonous stack（单调栈）

这是单调栈，经典的数据结构之一，单调栈的目的就是为了查找下一个更大/小的元素，步骤如下：

1. 如果栈为空，或者栈顶元素大于当前元素时，push当前元素到栈顶；
2. 如果栈不为空，且栈顶元素小于当前元素时，一直pop，直到栈为空或者栈顶元素大于当前元素。

注意：上面说的“下一个更大/更小元素”并不绝对，重要的是单调栈是什么样子的，找下一个更大更小元素只是其中一个应用，其他更多的应用还有很多！！！例如LeetCode 456. 132 Pattern!!!这点一定要注意！！！要深入理解数据结构，而不是单一问题。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 找到nums2里所有元素的next greater element，由于无重复元素，因此用hashmap来存储，然后对nums1进行循环get即可。
        Stack<Integer> stack = new Stack();
        Map<Integer, Integer> dict = new HashMap();

        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                dict.put(stack.pop(), num);
            }
            stack.push(num);
        }

        // stack里剩下的说明都是没有next greater element的数字
        while (!stack.isEmpty()) {
            dict.put(stack.pop(), -1);
        }

        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = dict.get(nums1[i]);
        }

        return nums1;
    }
}