155. 最小栈

题目描述

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

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

解题思路

常数时间内检索到最小元素的栈，则需要以空间换时间，创建另一个栈保存当前情况下的栈的最小值。

代码如下：

class MinStack {
    List<Integer> helper;
  List<Integer> list;
  int min;

  /** initialize your data structure here. */
  public MinStack() {
    list = new ArrayList<>();
      helper = new ArrayList<>();
      min = Integer.MAX_VALUE;
  }

  public void push(int val) {
    list.add(val);
    if (min>val){
      min = val;
    }
    helper.add(min);
  }

  public void pop() {
      int index = list.size() - 1;
      list.remove(index);
    helper.remove(index);
    if (helper.size() == 0){
        min = Integer.MAX_VALUE;
    }else {
        min = helper.get(index-1);
    }
  }

  public int top() {
      return list.get(list.size() - 1);
  }

  public int getMin() {
      return helper.get(helper.size() - 1);

  }
}

运行结果：

14:06    info
                        解答成功:
                        执行耗时:9 ms,击败了17.46% 的Java用户
                        内存消耗:40.2 MB,击败了56.99% 的Java用户

小结

用list代替stack操作，时间上还是不大理想