I just attempted the Maximum Element Challenge on Hackerrank. This question has been posted before in swift Swift Hackerrank Maximum Element in a Stack but it has attracted low views/no answers. Moving forward, based on the requirements of finding the maximum element, I used a vector<int>
as my underlying data structure as opposed to using Stack
as I can't iterate through a stack. This exercise is meant to be a simple one but the time limit gets exceeded for larger input.
How do I improve the performance? Please feel free to criticise my approach as I'm new to C++ with 5 days of experience.
You have an empty sequence, and you will be given \$N\$ queries. Each query is one of these three types:
- 1 x -Push the element x into the stack
- 2 -Delete the element present at the top of the stack
- 3 -Print the maximum element in the stack
Input Format
The first line of input contains an integer, \$N\$ . The next \$N\$ lines each contain an above mentioned query. (It is guaranteed that each query is valid.)
Constraints
- \$1 \leq N \leq 10^5 \$
- \$1 \leq x \leq 10^9 \$
- \$1 \leq \text{type} \leq 3 \$
Output Format
For each type \$3\$ query, print the maximum element in the stack on a new line.
Sample Input
10 1 97 2 1 20 2 1 26 1 20 2 3 1 91 3
Sample Output
26 91
#include <vector>
#include <iostream>
#include <algorithm>
//using namespace std;
bool compareValues(int i, int j) { return i<j; }
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int N;
int queryType;
int element;
std::vector<int> stackOfNumbers;
std::cin >> N;
for(int i =0; i < N ; i++){
std::cin >> queryType;
switch(queryType) {
case 1 :
std::cin >> element;
stackOfNumbers.push_back(element);
break;
case 2 :
stackOfNumbers.erase(stackOfNumbers.end()-1);
break;
case 3 :
std::cout<< *std::max_element(std::begin(stackOfNumbers), std::end(stackOfNumbers),compareValues ) << std::endl;
break;
default :
std::cout << "Invalid queryType" << std::endl;
}
}
return 0;
}