This C++ program finds the next greater element for each element in an array. The next greater element for an element x is the first greater element on the right side of x in the array. If no such element exists, the output is -1 for that element.
Program Code
#include <iostream>
#include <vector>
#include <stack>
std::vector<int> findNextGreaterElements(const std::vector<int>& nums) {
std::vector<int> result(nums.size(), -1); // Initialize result vector with -1
std::stack<int> s; // Stack to keep track of elements indices
for (int i = 0; i < nums.size(); i++) {
while (!s.empty() && nums[s.top()] < nums[i]) {
result[s.top()] = nums[i];
s.pop();
}
s.push(i);
}
return result;
}
int main() {
std::vector<int> nums = {4, 5, 2, 25};
std::vector<int> result = findNextGreaterElements(nums);
std::cout << "Array: ";
for (int num : nums) std::cout << num << " ";
std::cout << "\\nNext Greater Elements: ";
for (int res : result) std::cout << res << " ";
std::cout << std::endl;
return 0;
}
Function Documentation
std::vector<int> findNextGreaterElements(const std::vector<int>& nums)
- Parameters:
nums– a vector of integers representing the array. - Returns: A vector of integers where each element is the next greater element of the corresponding input element.
- Description: This function iterates through the array, using a stack to keep track of the array indices of elements for which a greater next element has not yet been found. For each element, it resolves the next greater elements of all elements in the stack that are less than the current element.
Example Usage
std::vector<int> nums = {4, 5, 2, 25};
std::vector<int> result = findNextGreaterElements(nums);
// Output will display:
// Array: 4 5 2 25
// Next Greater Elements: 5 25 25 -1
