🌕 496. 下一个更大元素 I

难度: 🌕

问题描述

---

解法

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 思路：
        // 单调栈，遍历一遍 nums2 求出所有元素的下一个更大元素
        // 并存 map 
        // 遍历 nums1，找到 map 中的结果，进行填充
        LinkedList<Integer> stack = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i : nums2) {
            if(stack.isEmpty()) {
                stack.push(i);
            } else {
                // stack 非空
                int peek = stack.peek();
                if(i > peek) {
                    while(!stack.isEmpty() && i > stack.peek()) {
                        int tmp = stack.pop();
                        map.put(tmp, i);
                    }
                    stack.push(i);
                } else {
                    stack.push(i);
                }
            }
        }
        // 遍历 nums1
        int len = nums1.length;
        int[] res = new int[len];
        for(int i = 0; i < len; i ++) {
            if(!map.containsKey(nums1[i])) {
                res[i] = -1;
            } else {
                res[i] = map.get(nums1[i]);
            }
        }
        return res;
    }
}

---

输出