Next Greater Element 1
[題目]
https://leetcode.com/problems/next-greater-element-i/
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
例如, num1[1]是1，所以num2中的1，在num2中的下一個大於1的值是nums[2]=4
[Solution]
Steps :
1. Find "Next greater element" for all element in nums2.
2. Use a hash map to record <value, next greater element value>
[Solution]
Steps :
1. Find "Next greater element" for all element in nums2.
2. Use a hash map to record <value, next greater element value>
3. For each element in num1, check it's 'next greater element value' by look up hash map.
And the most difficult and important is step 1.
Push element from "right to left" to min top monotonic stack
Then NGE will be in the min top mono stack
1. push element in nums2 from RIGHT to LEFT (<---) into mono Stack
2. decrease Monotonic stack operation :
Before pushing new element 'e' into Stack, pop out all the element smaller the 'e'.
Pop them because of below reasons :
A.Pop them is safe, because they are smaller than 'e', so useless for 'e' and all elements on the left of 'e'.
A.Pop them is safe, because they are smaller than 'e', so useless for 'e' and all elements on the left of 'e'.
B.If we don't pop, they will become redundant elements, and delay us to find closest and greater element on right side.
After popping, the top() will be the next greater element of 'e'.
Take '4' as example : we have monoStack (2] and wanna find next greater element for '4'.
As explained below, '2' is useless for '4' and element on left of '4'.
So pop out '2' is safe. We don't need it in the future.
Pop smaller elements is necessary because if we don't, we will have to check all of useless element when finding NGE.
For example, the nums2=[1,3,4,2]
check 2's NGE : none, and monoS became (2]
check 4's NGE : none, and monoS became (4]
check 3's NGE : we got '4', and monoS became (3,4]
check 3's NGE : we got '4', and monoS became (3,4]
check 1's NGE : we got '3', and monoS became (1,3,4]
[Code]
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> ans;
stack<int> stk;
unordered_map<int,int> ht;//num, the next greater num
for(auto i:nums){
while(!stk.empty() && stk.top() < i){
ht[stk.top()]=i;//record the "next greater" on hashtable
stk.pop();
}
stk.push(i);
}
for(auto i:findNums){
if(ht.find(i)==ht.end()) ans.push_back(-1);
else ans.push_back(ht[i]);
}
return ans;
}
};
