[C++] 99.74% faster | Simple, Better and Optimal solutions using stacks
Simple Solution\n\nUsing Stack and Multiset Approach (RunTime : 56 ms (43.75%) & Memory Usage : 35.5%)\nIdea behind this logic is to have one stack todo stack o
### Simple Solution\n\n**Using Stack and Multiset Approach** *(RunTime : 56 ms (43.75%) & Memory Usage : 35.5%)*\nIdea behind this logic is to have one stack todo stack operations and multiset to get min element\n\n```\n\tclass MinStack {\n\tpublic:\n\t\tstack<int>s;\n\t\tmultiset<int>m;   \n\n\t\tvoid push(int val) {//insert elements on both set and stack\n\t\t\ts.push(val); \n\t\t\tm.insert(val);\n\t\t}\n\n\t\tvoid pop() {//poping elements on both set and stack\n\t\t\tint top = s.top();\n\t\t\ts.pop();\n\t\t\tm.erase(m.find(top)); \n\t\t}\n\n\t\tint top() { //return stack top\n\t\t\treturn s.top();\n\t\t}\n\n\t\tint getMin() {// return set first element \n\t\t\treturn *m.begin();\n\t\t}\n\t};\n```\n\n### Better Solution\n\n**Using Two Stack Approach** *(RunTime : 16 ms (97.50%) & Memory Usage : 78.95%)*\nThe logic is to have one stack todo stack operations and another stack to store history of min elements.\n\n```\n\tclass MinStack {\n\tpublic:\n\t\tstack<int>s,minKeeper;\n\t\tvoid push(int val) {\n\t\t\ts.push(val); // push val in stack\n\n\t\t\tif(minKeeper.size()==0||val<=minKeeper.top()){//push in when empty or lesser than current minElement\n\t\t\t\tminKeeper.push(val);\n\t\t\t}\n\t\t}\n\n\t\tvoid pop() {\n\n\t\t\tif(minKeeper.top() == s.top())//pop when last element was min element \n\t\t\t\tminKeeper.pop();\n\t\t\ts.pop();\n\t\t}\n\n\t\tint top() {//return top of stack\n\t\t\treturn s.top();\n\t\t}\n\n\t\tint getMin() {//return top of minKeeper\n\t\t\treturn minKeeper.top();\n\t\t}\n\t};\n```\n\n### Optimal Solution\n**Using only One stack** *(RunTime : 12 ms (99.74%) & Memory Usage :88.88%)*\n```\n\tclass MinStack {\n\tpublic:\n\t\tstack<int>s;\n\t\tint minElement = INT_MAX;//initalize with max value\n\n\t\tvoid push(int val) {\n\t\t\tif(minElement>=val){// whenever val is lesser than current minElement, store current minElement in stack and make val as current minElement\n\t\t\t\ts.push(minElement);\n\t\t\t\t minElement = val;\n\t\t\t}\n\t\t\t  s.push(val);\n\t\t}\n\n\t\tvoid pop() {\n\t\t\tif(minElement==s.top()){//top is minElement then previous element will be previous minElement, so pop and store current top as current MinElement\n\t\t\t\ts.pop();\n\t\t\t\tminElement = s.top();\n\t\t\t}\n\t\t\ts.pop();\n\t\t}\n\n\t\tint top() {// return stack top\n\t\t\treturn s.top();\n\t\t}\n\n\t\tint getMin() {//return minElement\n\t\t\treturn minElement;\n\t\t}\n\t};\n```\n\n\n\nThank you\n\n```\n\t\tif(Useful == true)\n\t\t\tupvote();\n\t\telse\n\t\t\tcomment();\n```\n\nBy \uD83D\uDC93 JS
[]