力扣496. 下一个更大元素 I

本文主要是介绍力扣496. 下一个更大元素 I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;}
}

这篇关于力扣496. 下一个更大元素 I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---