題目描述

給定兩個 沒有重復元素 的數(shù)組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每個元素在 nums2 中的下一個比其大的值。

nums1 中數(shù)字 x 的下一個更大元素是指 x 在 nums2 中對應位置的右邊的第一個比 x 大的元素。如果不存在，對應位置輸出 -1 。

496. 下一個更大元素Ⅰ

解法

構(gòu)造一個單調(diào)棧：從棧頂?shù)綏５椎脑貑握{(diào)不減，每當遇到一個比棧頂元素大的，說明棧中所有元素的下一個更大元素是當前元素，將所有元素出棧并存在HashMap里。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<>();
        LinkedList<Integer> stack = new LinkedList<>();
        for(int a : nums2){
            //注意循環(huán)條件
            //棧為空沒有比較必要，元素入棧；
            //棧不空但元素 a 比棧頂元素小，繼續(xù)入棧元素；
            //棧不空且元素 a 比棧頂大，所有元素出棧，結(jié)果存入HashMap中
            while(!stack.isEmpty() && stack.peek() < a){
                map.put(stack.pop(), a);
            }
            stack.push(a);
        }

        int[] res = new int[nums1.length];
        for(int i = 0; i < res.length; i++){
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}