155. Min Stack 最小栈

@TOC

# 题目描述

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.

Example:

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

# 解题方法

# 栈同时保存当前值和最小值

1. 新元素入栈：当栈为空，保存元组 `(x, x)`；当栈不空，保存元组 `(x, min(此前栈内最小值， x)))`
2. 出栈：删除栈顶的元组。
``````class MinStack(object):

def __init__(self):
"""
"""
self.stack = []

def push(self, x):
"""
:type x: int
:rtype: void
"""
if not self.stack:
self.stack.append((x, x))
else:
self.stack.append((x, min(x, self.stack[-1][1])))

def pop(self):
"""
:rtype: void
"""
self.stack.pop()

def top(self):
"""
:rtype: int
"""
return self.stack[-1][0]

def getMin(self):
"""
:rtype: int
"""
return self.stack[-1][1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
``````

# 辅助栈

# 同步栈

``````class MinStack(object):

def __init__(self):
"""
"""
self.stack = []
self.min = []

def push(self, x):
"""
:type x: int
:rtype: void
"""
self.stack.append(x)
if not self.min:
self.min.append(x)
else:
self.min.append(min(self.min[-1], x))

def pop(self):
"""
:rtype: void
"""
self.stack.pop()
self.min.pop()

def top(self):
"""
:rtype: int
"""
return self.stack[-1]

def getMin(self):
"""
:rtype: int
"""
return self.min[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
``````

C++代码如下：

``````class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}

void push(int x) {
if (!mins.empty() && x > mins.top()) {
mins.push(mins.top());
} else {
mins.push(x);
}
values.push(x);
}

void pop() {
values.pop();
mins.pop();
}

int top() {
return values.top();
}

int getMin() {
return mins.top();
}
private:
stack<int> values;
stack<int> mins;
};

/**
* 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();
*/
``````

# 不同步栈

1. 当插入元素 x 小于等于辅助栈的栈顶元素时，才把 x 插入到辅助栈的栈顶。
2. 当弹出的元素 x 等于辅助栈的栈顶元素时，才把辅助栈的栈顶也弹出。

C++ 代码如下：

``````class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}

void push(int x) {
st.push(x);
if (min_values.size() == 0) {
min_values.push(x);
} else {
if (x <= min_values.top()) {
min_values.push(x);
}
}
}

void pop() {
int cur = st.top();
st.pop();
if (cur == min_values.top()) {
min_values.pop();
}
}

int top() {
return st.top();
}

int getMin() {
return min_values.top();
}
private:
stack<int> st;
stack<int> min_values;
};

/**
* 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();
*/
``````

# 日期

2018 年 2 月 4 日 2018 年 11 月 24 日 —— 周六快乐 2019 年 9 月 18 日 —— 今日又是九一八