题目描述

  • 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

解析

  • 在数据栈的基础上维护一个用来存放最小值的辅助栈
  • 每次入栈，新入栈的元素都要和辅助栈栈顶元素比较，如果新入栈的元素更小，就让它也加入最小栈中，否则最小栈再次压入其栈顶元素
  • 每次出栈，数据栈和辅助栈同时弹出元素
  • 这样就可以保证在任何情况下，辅助栈栈顶元素始终是数据栈中的最小元素

代码实现

  1. public class MinFunctionStack{
  3.     Stack<Integer> data = new Stack<Integer>();
  4.     Stack<Integer> assist = new Stack<Integer>();
  6.     public void push(int node) {
  7.         data.push(node);
  8.         if(assist.size() == 0 || node < assist.peek()){
  9.             assist.push(node);
  10.         }else{
  11.             assist.push(assist.peek());
  12.         }
  13.     }
  15.     public void pop() {
  16.         if(data.size() > 0 && assist.size() > 0){
  17.             data.pop();
  18.             assist.pop();
  19.         }
  20.     }
  22.     public int top() {
  23.         if(data.size() > 0){
  24.             return data.peek();
  25.         }
  26.         return Integer.MIN_VALUE;
  28.     }
  30.     public int min() {
  31.         if(data.size() > 0 && assist.size() > 0){
  32.             return assist.peek();
  33.         }
  34.         return Integer.MIN_VALUE;
  35.     }
  37. }