LeetCode Min Stack-白红宇

LeetCode Min Stack

阅读量：5306 次

发布时间：2019-06-14

本文共 2103 字，大约阅读时间需要 7 分钟。

原题链接在这里:

题目：

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.

题解：

可以用另一个stack, min_stk来维护最小值. push()时检测x是否小于等于min_stk 的peek(), 若true，则同时push进min_stk.

pop()时若该值等于min_stk.peek()则同时对min_stk进行pop()操作。

getMin()返回min_stk.peek()即可。

Note:使用peek(), pop()之前，都要检测stack.isEmpty(), 否则会throw exception.

Time Complexity: getMin(), O(1); push(), O(1); pop(), O(1); top(), O(1).

Space: O(n).

AC Java:

1 public class MinStack { 2  3     Stack
     
       stk; 4     Stack
      
        minStk; 5     public MinStack() { 6         stk = new Stack
       
        (); 7         minStk = new Stack
        
         (); 8     } 9     10     public void push(int x) {11         stk.push(x);12         if(minStk.isEmpty() || minStk.peek()>=x){13             minStk.push(x);14         }15     }16     17     public void pop() {18         if(!stk.isEmpty()){19             int x = stk.pop();20             if(!minStk.isEmpty() && x == minStk.peek()){21                 minStk.pop();22             }23         }24     }25     26     public int top() {27         if(!stk.isEmpty()){28             return stk.peek();29         }30         throw new IllegalStateException("Stack is empty!");31     }32     33     public int getMin() {34         if(!minStk.isEmpty()){35             return minStk.peek();36         }37         throw new IllegalStateException("Stack is empty!");38     }39 }40 41 /**42  * Your MinStack object will be instantiated and called as such:43  * MinStack obj = new MinStack();44  * obj.push(x);45  * obj.pop();46  * int param_3 = obj.top();47  * int param_4 = obj.getMin();48  */