LeetCode: Min Stack 解题报告-白红宇

LeetCode: Min Stack 解题报告

阅读量：6585 次

发布时间：2019-06-24

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

Min Stack

Question

Solution

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.

Show Tags

Have you met this question in a real interview? Yes No

SOLUTION 1:

比较直观。用一个min stack专门存放最小值，如果有比它小或是相等的（有多个平行的最小值都要单独存放，否则pop后会出问题），

则存放其到minstack.具体看代码：

1 class MinStack { 2     Stack
      
        elements = new Stack
       
        (); 3     Stack
        
          minStack = new Stack
         
          (); 4      5     public void push(int x) { 6         elements.push(x); 7         if (minStack.isEmpty() || x <= minStack.peek()) { 8             minStack.push(x); 9         }10     }11 12     public void pop() {13         if (elements.isEmpty()) {14             return;15         }16         17         // 这个地方太蛋疼了，居然要用equals...18         if (elements.peek().equals(minStack.peek())) {19             minStack.pop();20         }21         elements.pop();22     }23 24     public int top() {25         return elements.peek();       26     }27 28     public int getMin() {29         return minStack.peek();30     }31 }

View Code

2014.1229 redo.

1 class MinStack { 2     Stack
      
        s = new Stack
       
        (); 3     Stack
        
          min = new Stack
         
          (); 4      5     public void push(int x) { 6         s.push(x); 7         if (min.isEmpty() || x <= min.peek()) { 8             min.push(x); 9         }10     }11     12     // Pop 1: use equals.13     public void pop1() {14         // BUG 1: Very very trick. we should use EQUALS here instead of  "=="15         if (s.peek().equals(min.peek())) {16             min.pop();17         }18         s.pop();19     }20     21     // Pop 2: use int22     public void pop2() {23         // BUG 1: Very very trick. we should use EQUALS here instead of  "=="24         int n1 = s.peek();25         int n2 = min.peek();26         if (n1 == n2) {27             min.pop();28         }29         s.pop();30     }31     32     // Pop 3: use (int)33     public void pop() {34         // BUG 1: Very very trick. we should use EQUALS here instead of  "=="35         if ((int)s.peek() == (int)min.peek()) {36             min.pop();37         }38         s.pop();39     }40 41     public int top() {42         return s.peek();43     }44 45     public int getMin() {46         return min.peek();47     }48 }