【一天一道LeetCode】#155. Min Stack

2016-07-09

（一）题目

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

push(x) &ndash; Push element x onto stack.

pop() &ndash; Removes the element on top of the stack.

top() &ndash; Get the top element.

getMin() &ndash; Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); &ndash;> Returns -3.
minStack.pop();
minStack.top(); &ndash;> Returns 0.
minStack.getMin(); &ndash;> Returns -2.

（二）解题

class MinStack {
public:
/** initialize your data structure here. */
stack datastack;//存储数据
stack minstack;//存储最小栈
MinStack() {

}
void push(int x) {
datastack.push(x);//压入数据
if(minstack.empty()) minstack.push(x);//如果最小栈为空直接压入
else if(x<=minstack.top()) minstack.push(x);//如果当前压入的值小于等于最小栈的栈顶元素，则压入最小栈
}

void pop() {
if(datastack.top()==minstack.top()) minstack.pop();//如果数据栈和最小栈的栈顶元素相等，则最小栈栈顶元素弹出
datastack.pop();//数据栈弹出元素

}

int top() {
return datastack.top();//返回栈顶元素
}

int getMin() {
return minstack.top();//返回最小栈栈顶元素
}
};
/**
* 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();
*/