首页 > 代码库 > LeetCode: Min Stack 解题报告

LeetCode: Min Stack 解题报告

2024-08-02 23:46:40   219人阅读

Min Stack

My Submissions

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

 

Discuss

SOLUTION 1:

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

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

 1 class MinStack { 2     Stack<Integer> elements = new Stack<Integer>(); 3     Stack<Integer> minStack = new Stack<Integer>(); 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

 

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/stack/MinStack.java

LeetCode: Min Stack 解题报告


联系
我们