496. Next Greater Element I - Easy

前往題目

想法

• 暴力解，用hashmap然後在nums2一個一個看

思路

1. 用hashmap儲存nums1中num和index的映射
2. 疊代nums2
3. 每次都檢查是否比stack的最上層還要大，如果是的話就pop，然後繼續比下一個上層，直到stack沒東西或是沒有比他大了，然後每次操作都要把該num放到相對應的index(藉助hashmap可以得知)
4. 最後如果當前數字有在nums1裡面代表需要找尋他的next greater value，所以push進去stack

這題不是暴力解的話根本不能算是easy，面試官會給暴力解過嗎😂奇怪的題目

Code

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // num -> index
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums1.length; ++i) {
            map.put(nums1[i], i);
        }
        // Result
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);

        // Monotonic stack
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums2.length; ++i) {
            // Current number
            int cur = nums2[i];
            
            // Found larger number
            while (!stack.isEmpty() && cur > stack.peek()) {
                // Get the larger number index
                int index = map.get(stack.pop());
                // Put the larger number into the position
                res[index] = cur;
            }

            // Push to stack if it's in nums1
            if (map.containsKey(cur)) {
                stack.push(cur);
            }
        }
        return res;
    }
}