# [LeetCode] 155. Min Stack 最小栈

2021年09月15日 阅读数：4

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

• 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:java

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.

Java: 2 Stackshtm

public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;

public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}

public void push(int number) {
stack.push(number);
if (minStack.empty() || minStack.peek >= number)
minStack.push(number);
}

public int pop() {
if (stack.peek().equals(minStack.peek()) )
minStack.pop();
return stack.pop();
}

public int min() {
return minStack.peek();
}
}

Java: 2 Stacksblog

public class MinStack {
private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();

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

public void push(int x) {
s1.push(x);
if (s2.isEmpty() || s2.peek() >= x) s2.push(x);
}

public void pop() {
// Cannot write like the following:
// if (s2.peek() == s1.peek()) s2.pop();
// s1.pop();
int x = s1.pop();
if (s2.peek() == x) s2.pop();
}

public int top() {
return s1.peek();
}

public int getMin() {
return s2.peek();
}
}

Java: 1 Stackelement

public class MinStack {
private int min_val = Integer.MAX_VALUE;
private Stack<Integer> s = new Stack<>();

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

public void push(int x) {
if (x <= min_val) {
s.push(min_val);
min_val = x;
}
s.push(x);
}

public void pop() {
if (s.pop() == min_val) min_val = s.pop();
}

public int top() {
return s.peek();
}

public int getMin() {
return min_val;
}
}

Python: 2 Stacks

class MinStack:
def __init__(self):
self.stack = []
self.minStack = []

def push(self, x):
self.stack.append(x)
if len(self.minStack) == 0 or x <= self.minStack[-1]:
self.minStack.append(x)

def pop(self):
if self.top() == self.getMin():
self.minStack.pop()
return self.stack.pop()

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

def getMin(self):
return self.minStack[-1]

Python: 1 Stack，最小值和元素一同入栈

class MinStack(object):

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

def push(self, x):
if x <= self.min:
self.stack.append(self.min)
self.min = x
self.stack.append(x)

def pop(self):
peak = self.stack.pop()
if peak == self.min:
self.min = self.stack.pop()

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

def getMin(self):
return self.min

Python: 1 Stack，记录差值

class MinStack(object):

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

def push(self, x):
if not self.stack:
self.min = x
self.stack.append(x - self.min)
if x < self.min:
self.min = x

def pop(self):
peak = self.stack.pop()
if peak < 0:
self.min = self.min - peak

def top(self):
if self.stack[-1] < 0:
return self.min
else:
return self.min + self.stack[-1]

def getMin(self):
return self.min

C++: 2 Stacks

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

void push(int x) {
s1.push(x);
if (s2.empty() || x <= s2.top()) s2.push(x);
}

void pop() {
if (s1.top() == s2.top()) s2.pop();
s1.pop();
}

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

int getMin() {
return s2.top();
}

private:
stack<int> s1, s2;
};

C++: 1 Stack

class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
min_val = INT_MAX;
}

void push(int x) {
if (x <= min_val) {
st.push(min_val);
min_val = x;
}
st.push(x);
}

void pop() {
int t = st.top(); st.pop();
if (t == min_val) {
min_val = st.top(); st.pop();
}
}

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

int getMin() {
return min_val;
}
private:
int min_val;
stack<int> st;
};