LeetCode Q155: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution:

The essence of this question is to solve the problem of getting minimum element in remaining stack. To solve it we need to keep track the min in current stack. So, each entry in the stack have to domains, first one is used to save value of current element. the second domain contains the min value under the current element in the stack.

	class MinStack {
	public:
	void push(int x) {
	if(myStack.size()==0){
	pair<int, int> e(x, x);
	myStack.push(e);
	}else{
	if(x<getMin()){
	pair<int, int> e(x, x);
	myStack.push(e);
	}else{
	pair<int, int> e(x, getMin());
	myStack.push(e);
	}
	}
	}
	void pop() {
	myStack.pop();
	}
	int top() {
	pair<int, int> e = myStack.top();
	return e.first;
	}
	int getMin() {
	pair<int, int> top=myStack.top();
	return top.second;
	}
	stack<pair<int, int> > myStack;
	};

view raw Q155MinStack.cpp hosted with ❤ by GitHub

Round 2 solution: Anther way to track minimum element in current array is to use another stack. Similar to sliding window problem, the element inserted to the stack has to be strictly smaller or equal to current top element of the stack.

	class MinStack {
	public:
	/** initialize your data structure here. */
	MinStack() {
	}
	void push(int x) {
	myStack.push(x);
	update(x);
	}
	void pop() {
	if(myStack.top()==helpStack.top())
	helpStack.pop();
	myStack.pop();
	}
	int top() {
	return myStack.top();
	}
	int getMin() {
	return helpStack.top();
	}
	void update(int x){
	if(helpStack.empty()||x<=helpStack.top())
	helpStack.push(x);
	}
	stack<int> myStack;
	stack<int> helpStack;
	};
	/**
	* Your MinStack object will be instantiated and called as such:
	* MinStack obj = new MinStack();
	* obj.push(x);
	* obj.pop();
	* int param_3 = obj.top();
	* int param_4 = obj.getMin();
	*/

view raw Q155Rnd2.cpp hosted with ❤ by GitHub