Problem: 496. 下一个更大元素 I

题目描述

思路

因为题目说nums1是nums2的子集，那么我们先把nums2中每个元素的下一个更大元素算出来存到一个映射里，然后再让nums1中的元素去查表即可

复杂度

时间复杂度:

$O(n1+n2)$；其中$n1$为数组nums1的大小,$n2$是数组nums2的大小

空间复杂度:

$O(n1)$

Code

class Solution {
    /**
     * Next Greater Element I
     *
     * @param nums1 Given array
     * @param nums2 Given array
     * @return int[]
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] greater = nextGreaterElement(nums2);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; ++i) {
            map.put(nums2[i], greater[i]);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < res.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    /**
     * Monotonic stack template
     *
     * @param nums Given array
     * @return int[]
     */
    private int[] nextGreaterElement(int[] nums) {
        int len = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[len];
        for (int i = len - 1; i >= 0; --i) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return res;
    }
}