力扣496. 下一个更大元素 I
Problem: 496. 下一个更大元素 I
文章目录
- 题目描述
- 思路
- 复杂度
- Code
题目描述
思路
因为题目说nums1是nums2的子集，那么我们先把nums2中每个元素的下一个更大元素算出来存到一个映射里，然后再让nums1中的元素去查表即可
复杂度
时间复杂度:
O ( n 1 + n 2 ) O(n1 + n2) O(n1+n2)；其中 n 1 n1 n1为数组nums1的大小, n 2 n2 n2是数组nums2的大小
空间复杂度:
O ( n 1 ) O(n1) 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;}
}