categories: leetcode

155.png

题目描述

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

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

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.

参考代码

  1. class MinStack {
  2.         private Stack<Integer> stackData;
  3.         private Stack<Integer> stackMin;
  4.     /** initialize your data structure here. */
  5.     public MinStack() { 
  6.         stackData = new Stack<Integer>();
  7.         stackMin = new Stack<Integer>();
  8.     }
  10.     public void push(int x) {
  11.         stackData.push(x);
  12.         if(stackMin.isEmpty() || x <= stackMin.peek()) {//最小值栈的为空或这最小值小于等于
  13.             stackMin.push(x);
  14.         } 
  15.     }
  17.     public void pop() {
  18.         Integer num = stackData.pop();
  19.         if(num.equals(stackMin.peek())) {//要用equals函数
  20.             stackMin.pop();
  21.         }
  23.     }
  25.     public int top() {
  26.             return stackData.peek();
  27.     }
  29.     public int getMin() {
  30.             return stackMin.peek();
  31.     }
  32. }
  34. /**
  35.  * Your MinStack object will be instantiated and called as such:
  36.  * MinStack obj = new MinStack();
  37.  * obj.push(x);
  38.  * obj.pop();
  39.  * int param_3 = obj.top();
  40.  * int param_4 = obj.getMin();
  41.  */

思路及总结

利用两个栈，一个代表最小值，一个代表普通情况。注意最小值栈要依靠普通栈，普通栈中最小值出栈，最小值栈的最小值也要出栈。另外自己基础太差，wrong answer的时候一直没发现要用equals才能进行更合理的比较。希望自己以后更深入的时候能有更好的理解。
image.png

参考

https://blog.csdn.net/loophome/article/details/83749444
https://blog.csdn.net/returnzhang/article/details/78608898