# 496. Next Greater Element I

You are given two arrays (without duplicates) `nums1` and `nums2` where `nums1`’s elements are 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, output -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.
``````

Note:

1. All elements in `nums1` and `nums2` are unique.
2. The length of both `nums1` and `nums2` would not exceed 1000.

``````class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> res(findNums.size());
for (int i = 0; i < findNums.size(); ++i) {
int j = 0, k = 0;
for (; j < nums.size(); ++j) {
if (nums[j] == findNums[i]) break;
}
for (k = j + 1; k < nums.size(); ++k) {
if (nums[k] > nums[j]) {
res[i] = nums[k];
break;
}
}
if (k == nums.size()) res[i] = -1;
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> res(findNums.size());
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
m[nums[i]] = i;
}
for (int i = 0; i < findNums.size(); ++i) {
res[i] = -1;
int start = m[findNums[i]];
for (int j = start + 1; j < nums.size(); ++j) {
if (nums[j] > findNums[i]) {
res[i] = nums[j];
break;
}
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> res;
stack<int> st;
unordered_map<int, int> m;
for (int num : nums) {
while (!st.empty() && st.top() < num) {
m[st.top()] = num; st.pop();
}
st.push(num);
}
for (int num : findNums) {
res.push_back(m.count(num) ? m[num] : -1);
}
return res;
}
};
``````

Next Greater Element II

Next Greater Element III

Daily Temperatures

https://leetcode.com/problems/next-greater-element-i

https://leetcode.com/problems/next-greater-element-i/discuss/97676/java-solution-with-hashmap

https://leetcode.com/problems/next-greater-element-i/discuss/97595/java-10-lines-linear-time-complexity-on-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation