leetcode155. 最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

思路：辅助栈。跟着主栈压和弹，但是压入的是当前最小值。取最小值时就取辅助栈的栈顶即可。

  

   

    

     

    
    

     

      import java.util.Stack;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class MinStack {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 // 数据栈
     
    
   

    

     

    
    

     
 private Stack<Integer> data;
     
    
   

    

     

    
    

     
 // 辅助栈
     
    
   

    

     

    
    

     
 private Stack<Integer> helper;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 /**
     
    
   

    

     

    
    

     

       * initialize your data structure here.
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
 public MinStack() {
     
    
   

    

     

    
    

     

       data = new Stack<>();
     
    
   

    

     

    
    

     

       helper = new Stack<>();
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public void push(int x) {
     
    
   

    

     

    
    

     

       data.add(x);
     
    
   

    

     

    
    

     
 if (helper.isEmpty() || helper.peek() >= x) {
     
    
   

    

     

    
    

     

       helper.add(x);
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     

       helper.add(helper.peek());
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public void pop() {
     
    
   

    

     

    
    

     

       helper.pop();
     
    
   

    

     

    
    

     

       data.pop();
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 public int top() {return data.peek();}
     
    
   

    

     

    
    

     
 public int getMin() {return helper.peek();}
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103564237