LeetCode-496. Next Greater Element I
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.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4] Output: [3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3. - 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.
Constraints:
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 10^4- All integers in?
nums1?and?nums2?are?unique. - All the integers of?
nums1?also appear in?nums2.
【C++】
1. vector
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
vector<int> res(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;
}
};2. stack
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> st;
int n = nums2.size();
map<int,int> v;
for (int i = n-1; i>=0; i--) {
if (st.empty()) {
v[nums2[i]] = -1;
st.push(nums2[i]);
} else {
while (!st.empty() && st.top() <= nums2[i]) {st.pop();}
if (st.empty()) {v[nums2[i]] = -1;}
else {v[nums2[i]] = st.top();}
st.push(nums2[i]);
}
}
n = nums1.size();
vector<int> ans(n);
for (int i=0;i<n;i++) {ans[i] = v[nums1[i]];}
return ans;
}
};【Java】
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
int[] ans = new int[n1];
// To hold the numbers in the right which can be greater than current number
Stack<Integer> stack = new Stack<>();
// To store the mapping of number with it's greater number in right
Map<Integer,Integer> greaterInRight = new HashMap<>();
// Iterate from last number to the first number
for(int i=n2-1; i>=0; i--) {
// Remove numbers from top of the stack until a greater number is found
while( !stack.isEmpty() && stack.peek() < nums2[i] ) {
stack.pop();
}
/* If a stack is not empty, then the top of the stack contains the greater
number than current number, else there is no number in right which is
greater than current number */
greaterInRight.put(nums2[i], stack.isEmpty() ? -1 : stack.peek() );
/* Push current number into stack, as this number can be greater number
for the numbers in left */
stack.push( nums2[i] );
}
// Use the map to get the number in right greater than each number in {nums1}
for(int i=0; i<n1; i++) {
ans[i] = greaterInRight.get( nums1[i] );
}
return ans;
}
}
