CodingInterview/minStack.cpp at master · ssripadham/CodingInterview · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <stack>
#include <map>
#include <utility>
#include <climits>
#include <iostream>

using  namespace std;


class MiniStack {

public:

	MiniStack(){
		myStack = new stack<int>();
		minStack = new stack<pair<int,int>>();
	}

	void push(int  val){
		if (minStack->empty()){
			minStack->push(make_pair(val, 0));
		} else {
			int minSoFar = minStack->top().first;

			if (val < minSoFar) {
				minStack->push(make_pair(val, myStack->size()));
			}
		}
		myStack->push(val);
	}

	int top(){
		myStack->top();
	}


	void pop() {

		if (myStack->empty()){
			return;
		}

		int topElem = myStack->top();

		int topElemInMinStack = minStack->top().first;

		if (topElemInMinStack == topElem){

			if (myStack->size() -1 <= minStack->top().second) {
				minStack->pop();
			}
		}

		myStack->pop();
	}

	int minVal() {

		if (minStack->empty()){
			return INT_MIN;
		}
		return minStack->top().first;
	}

	bool isEmpty(){
		return myStack->empty();
	}

	~MiniStack() {
		delete myStack;
	}

private:

	stack<int> * myStack;
	stack<pair<int,int>> * minStack;

};

int main(){
	MiniStack s;
	s.push(8);
	s.push(2);
	s.push(1);
	s.push(1);
	s.push(1);
	s.pop();
	s.pop();
	s.pop();
	s.pop();
	cout<<s.minVal()<<endl;
	return 1;
}