- Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
- This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
Leetcode -496- Next larger element I
[Blog link]
The path to learning at 🐔
The nuggets home page
[答 案]
Topic link
[making address]
Making the address
[B].
You are given two arrays with no duplicate elements, nums1 and nums2, where nums1 is a subset of nums2.
Find the next value greater in nums2 for each element in nums1.
The next larger element of the number x in nums1 is the first larger element of x to the right of the corresponding position in nums2. If no, -1 is displayed at the corresponding position.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. For the number 4 in num1, you cannot find the next larger number in the second array, so print -1. For the number 1 in num1, the next large number to the right of the number 1 in the second array is 3. For the number 2 in num1, there is no next larger number in the second array, so -1 is output.Copy the code
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4]. For the number 2 in num1, the next large number in the second array is 3. For the number 4 in num1, there is no next larger number in the second array, so -1 is output.Copy the code
Tip:
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 104
- All integers in nums1 and nums2 are different
- All integers in nums1 also appear in nums2
Advanced: Can you design a time complexity O(nums1.length + nums2.length) solution?
Idea 1: violent search
- The simplest is definitely a violent search
- Just do it once for every round
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[] res = new int[m];
for (int i = 0; i < m; ++i) {
int j = 0;
while(j < n && nums2[j] ! = nums1[i]) { ++j; }int k = j + 1;
while (k < n && nums2[k] < nums2[j]) {
++k;
}
res[i] = k < n ? nums2[k] : -1;
}
return res;
}
Copy the code
- Time complexity O(m* N)
- Space complexity O(1)
Idea 2: monotone stack
- Store numS2 elements in reverse order on the monotonic stack
- Records each element’s closest element greater than itself
- If you don’t have one, you put minus one
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for (int i = nums2.length-1; i >= 0; i--) {
int x = nums2[i];
while(! stack.isEmpty() && stack.peek() <= x) { stack.pop(); } map.put(x, stack.isEmpty() ? -1 : stack.peek());
stack.push(x);
}
int[] res = new int[nums1.length];
for (int i = 0; i < res.length; i++) {
res[i] = map.get(nums1[i]);
}
return res;
}
Copy the code
- Time complexity O(m+ N)
- Space complexity O(n)