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