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,
Digital rolling lottery program Keras Save and load model (JSON+HDF5) Remember once EventBus Project issues caused by memory leaks I've been drinking soft water for three years ? What is the use of soft water and water softener msf Generate Trojan horse attack android mobile phone Time conversion front desk will 2020-07-17T03:07:02.000+0000 Into 2020-07-17 11:07:02 Chuan Shen 1190 Reverses the substring between each pair of parentheses leetcodehive Summary of processing methods for a large number of small files SparkSQL Achieve partition overlay write Image format conversion