0496. Next Greater Element I¶
You are given two integer arrays nums1 and nums2 both of unique elements, where nums1 is a subset of nums2.
Find all the next greater numbers for nums1's elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Constraints:
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104- All integers in
nums1andnums2are unique. - All the integers of
nums1also appear innums2.
Follow up: Could you find an O(nums1.length + nums2.length) solution?
Analysis¶
The naive solution is doing two linear scans: for each element in nums1, we check the current element's index and find the first index from nums2 and return the element that it is pointing to. However, we want to improve this algorithm into O(n).
For almost all the "find next greater/less" type of problem, we can thinking about using a monotonic stack to solve it with O(n) time complexity. We basically want to build up a mapping between nums1[i] and nums2[j] where nums2[j] is the next immediate greater element to current nums1[i]. We can use a map to store this info. We also need a stack to mimic the monotonic stack operation.
For monotonic stack part, we can follow the below template:
for i, e in enumerate(arr):
while stack is not empty and stack top < e: # for "next greater"
stack.pop(0) # we remove the top since current element is the new "next greater"
"""ok, now we have the next greater element to arr[i-1], we could do something here
do your calculation"""
stack.push(e) # use for next iteration
As you can see, the worst case for the while loop to run multiple times is when we are having a decreasing order array followed by the last element being the greatest. However, don't forget for all the previous iterations, since the array is decreasing, we never get a chance to execute this while loop once (in all the previous iterations). So if you add it up, the precise complexity is O(2 \times n), which is still O(n).
Now we have a stack that records all the "next greater" element, and we want to know which element it was greater to. To build up the mapping, we simply add the map in between.
for i, e in enumerate(arr):
while stack is not empty and stack top < e: # for "next greater"
stack.pop(0) # we remove the top since current element is the new "next greater"
"""ok, now we have the next greater element to arr[i-1], we could do something here
do your calculation"""
# TODO: add to your map here
stack.push(e) # use for next iteration
Don't forget we also might see element that doesn't have element greater than itself, and those elements are storing in our stack. Reason is being we only keep the previous "unfounded yet" element in our stack. Using that info, we can correctly update our map to "-1".
Finally we just need to extract the map's info to a new array, which only takes O(n).
Note
Don't forget all the elements in nums1 are also in nums2, which means
all keys are avalible. So we don't need to update our map.
- Time: O(n)
- Space: O(n) for decreasing order
nums2case and the output array.
Code¶
class Solution {
public:
vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
stack<int> idx; // store current greater's index
map<int, int> mp;
for (int i = 0; i < nums2.size(); ++i) {
while (!idx.empty() && nums2[idx.top()] < nums2[i]) {
mp[nums2[idx.top()]] = nums2[i];
idx.pop();
}
idx.push(i);
}
while (!idx.empty()) {
mp[nums2[idx.top()]] = -1;
idx.pop();
}
vector<int> res(nums1.size());
for (int i = 0; i < nums1.size(); ++i) {
res[i] = mp[nums1[i]];
}
return res;
}
};