算法04-最小栈

算法栈最小栈

发布时间 : 2020-07-04 15:50

字数:903 阅读 :

评论:

题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。(这个是这道题的考察重点)

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

示例:

输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

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

1.如果我们不考虑在常数时间内检索到最小元素的栈的情况的话，我们可以使用集合来完成这道题，因为集合是有序可重复的(跟数组是类似的，只是封装了比数组更强大的一些功能)，只是我们在寻找最小值的时候是遍历的整个数组，时间复杂度就变大了，具体的实现如下:

class MinStack {
    private List<Integer> list;
    /** initialize your data structure here. */
    public MinStack() {
      //对象构造的时候才进行初始化
      list = new ArrayList<Integer>();
    }

    public void push(int x) {
      //将x入到list的末尾，一会儿直接获取末尾数字就能得到栈顶元素
      list.add(x);
    }

    public void pop() {
      //出栈，删除栈顶元素
      list.remove(list.size()-1);
    }

    public int top() {
      //查看栈顶元素
      return list.get(list.size()-1);
    }
      //主要是这里不满足我们的需求
    public int getMin() {
      //第一个作为最小的
      int min = list.get(0);
      for(int i : list){
        //如果有比第一个还小的，min 的值就更改为当前循环出来的值
        if(i<min){
          min = i;
        }
      }
      return min;
    }
}

2.显然我们第一种方法是不满足我们题目要求的，我们可以采用辅助栈的方式来进行存储，注意：当进行出栈的时候，如果数字栈出栈的数字跟最小栈的栈顶元素相同，此最小栈也要出栈

package com.cxy.stack;

import java.util.ArrayDeque;
import java.util.Deque;
/**
 * 设计一个支持 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.
 * 思想：每个数字入最小栈的时候先跟栈顶元素进行比较，如果比栈顶元素都小，入数字栈的同时要入最小栈
 */
public class MinStack {
  /** initialize your data structure here. */
  //数字栈
  private Deque<Integer> numStack;
  //最小栈
  private Deque<Integer> minStack;
  public MinStack() {
    //在调用构造函数的时候才进行对象的初始化,开辟内存空间
    numStack = new ArrayDeque<>();
    minStack = new ArrayDeque<>();
  }

  public void push(int x) {
    //每个数字入最小栈的时候先跟栈顶元素进行比较，如果比栈顶元素都小，入数字栈的同时要入最小栈
    numStack.push(x);
    if(minStack.size() ==0 || minStack.peek()>=x){
      minStack.push(x);
    }
  }

  public void pop() {
    //查看栈顶元素
    //弹出栈顶元素,numStack出栈的元素minStack栈顶元素一致时，minStack栈顶元素也要出栈
    int numPop = numStack.pop();
    if(numPop == minStack.peek()){
      minStack.pop();
    }
  }

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

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

我们这里最好使用Deque这种数据结构，而不用原生的Stack，因为当你一开始就输pop()出栈的话，栈为空，抛异常就导致程序终止了，当然我们也可以捕获这个异常做处理（我懒所以直接用Deque，哈哈哈）

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com