Topic overview ：

Design a support push,pop,top operation , The stack of the smallest element can be retrieved in a constant time .
push(x) – Element x Push into the stack .
pop() – Delete the elements at the top of the stack .
top() – Get stack top element .
getMin() – Retrieve the smallest element in the stack .

Examples

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> return -3.
minStack.pop();
minStack.top(); --> return 0.
minStack.getMin(); --> return -2.
class MinStack(object): def __init__(self): """ initialize your data structure
here. """ self.stack = [] # Store all elements self.minStack = [] #
When storing every pressed data , Minimum in stack （ If the value of the pushed data is greater than the minimum value in the stack, there is no need to repeatedly push the minimum value , If it is less than or equal to the minimum value in the stack, it needs to be pushed in ） def push(self,
x): """ :type x: int :rtype: void """ self.stack.append(x) if not self.minStack
or self.minStack[-1]>=x: self.minStack.append(x) def pop(self): #
When removing stack top elements , Determine whether to remove the minimum value in the stack """ :rtype: void """ if self.minStack[-1]==self.stack[-1]:
del self.minStack[-1] self.stack.pop() def top(self): """ :rtype: int """
return self.stack[-1] def getMin(self): """ :rtype: int """ return
self.minStack[-1]

Here are Java edition ：
1.class MinStack {   2.    // stack: store the stack numbers
3.    private Stack<Integer> stack = new Stack<Integer>();
4.    // minStack: store the current min values
5.    private Stack<Integer> minStack = new Stack<Integer>();   6.
7.    public void push(int x) {
8.        // store current min value into minStack
9.        if (minStack.isEmpty() || x <= minStack.peek())
10.            minStack.push(x);   11.        stack.push(x);   12.    }   13.
14.    public void pop() {
15.        // use equals to compare the value of two object, if equal, pop both of them
16.        if (stack.peek().equals(minStack.peek()))
17.            minStack.pop();   18.        stack.pop();   19.    }   20.
21.    public int top() {   22.        return stack.peek();   23.    }   24.
25.    public int getMin() {   26.        return minStack.peek();   27.    }
28.}
【 analysis 】

The crux of the problem is that minStack Design of ,push() pop() top() These operations Java Built in Stack All of them , without comment .

I initially thought about two more arrays , Record the first larger and the next smaller of each element separately , It's complicated .

Look at the code above for the first time , I think it's a problem , Why are you only here x<minStack.peek() Time pressure stack ? If ,push(5), push(1), push(3)
such minStack There is only one 5 and 1, such pop() Out 1 after , getMin()
No, you get it 5 instead of 3 Do you ? In fact, it is wrong to think so , Because if you want to pop() Out 1 before ,3 It's already been pop() Out ..

minStack The record is always the smallest of all the current elements , whether minStack.peek() stay stack Location in .

Technology
Daily Recommendation
views 2