496. Next Greater Element I.cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> nextGreater;
stack<int> s;
for (int num : nums2) {
while (!s.empty() && s.top() < num) {
nextGreater[s.top()] = num;
s.pop();
}
s.push(num);
}
vector<int> result;
for (int num : nums1) {
if (nextGreater.find(num) != nextGreater.end()) {
result.push_back(nextGreater[num]);
} else {
result.push_back(-1);
}
}
return result;
}
int main() {
vector<int> nums1 = {4, 1, 2};
vector<int> nums2 = {1, 3, 4, 2};
vector<int> result = nextGreaterElement(nums1, nums2);
for (int num : result) {
cout << num << " ";
}
cout << endl;
return 0;
}
Explanation:
- The code includes necessary libraries for input-output, vectors, unordered map, and stack.
- nextGreaterElement
function takes two vectors nums1
and nums2
as parameters.
- It creates an unordered map nextGreater
to store the next greater elements.
- Initializes a stack s
to keep track of potential next greater elements.
- It loops through nums2
and for each element:
- Compares the current element with elements in the stack.
- If the current element is greater than the top element in the stack, it updates the nextGreater
map with the pair (top element, current element) and pops the element from the stack.
- Pushes the current element onto the stack.
- Creates an empty result vector.
- Iterates through nums1
and checks if each element has a next greater element in the nextGreater
map.
- If found, pushes the next greater element to the result vector; otherwise, pushes -1.
- Returns the result vector.
- In the main
function, it defines nums1
and nums2
vectors.
- Calls nextGreaterElement
function with these vectors.
- Prints the elements of the result vector.