博文中会简要介绍Leetcode P0155题目分析及解题思路。
“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.
主体思路如下。维护两个栈，一个栈专门负责存储当前数据中的最小值，每次获取新元素后和这个最小栈的栈顶元素比较，若小于栈顶元素，则压入栈，否则再复制栈顶元素并将副本压入栈。第二个栈是普通的栈，用来存储所有的数据。这样在getMin的时候就可以知道当前数据下的最小值。
以下是Java的题解代码实现。
class MinStack {
Deque<Integer> stack;
Deque<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
this.stack = new LinkedList<>();
this.minStack = new LinkedList<>();
}
public void push(int x) {
int peek = Integer.MAX_VALUE;
if (!this.minStack.isEmpty())
peek = this.minStack.peekFirst();
// Build min stack
this.minStack.offerFirst((peek < x)? peek: x);
this.stack.offerFirst(x);
}
public void pop() {
this.minStack.pollFirst();
this.stack.pollFirst();
}
public int top() {
return this.stack.peekFirst();
}
public int getMin() {
return this.minStack.peekFirst();
}
}
以下是C++的题解代码实现。
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
int peek = INT_MAX;
if (!this->min_stack_.empty())
peek = this->min_stack_.top();
// Build min stack
this->min_stack_.push((peek < x)? peek: x);
this->int_stack_.push(x);
}
void pop() {
this->int_stack_.pop();
this->min_stack_.pop();
}
int top() {
return this->int_stack_.top();
}
int getMin() {
return this->min_stack_.top();
}
private:
stack<int> int_stack_;
stack<int> min_stack_;
};