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 .


MinStack minStack = new MinStack();
minStack.getMin(); --> return -3.
minStack.pop();; --> 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

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.    }  
【 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 .

©2019-2020 Toolsou All rights reserved,
VUE+Canvas Achieve desktop Pinball brick elimination games C/C++ Memory model 2019PHP Interview questions ( Continuously updated )PHPspringboot2 Separation of front and rear platforms ,token Put in header Pit for verification Vue SpringBoot conduct Excel download element-ui Step on pit record 45 The 12-year-old programmer was turned down , Is the workplace wrong ?Python Web frame Pandas Fundamentals of statistical analysis _ data processing (DataFrame Common operations )Java Misunderstanding —— Method overloading is a manifestation of polymorphism ?