Skip to content

Latest commit

 

History

History
172 lines (129 loc) · 7.16 KB

20190717_verymuch_最小栈和最小队列.md

File metadata and controls

172 lines (129 loc) · 7.16 KB
Raw

最小栈和最小队列

相信栈和队列这两种数据结构大家一定都不陌生吧。这两种数据结构有个特殊形式：即最小栈和最小队列。

下面我们分别来介绍下这两个带有“特异功能”的数据结构。

一、最小栈

1. 什么是最小栈

实现一个栈，带有出栈（pop），入栈（push），取最小元素（getMin）三个方法。并且这三个方法的时间复杂度都是O（1）。

2. 设计思路

2.1 错误思路

看了上面对于最小栈的定义后，可能大部分人都能够快速想得到这样的思路：

创建一个栈，再额外声明一个变量，用于存储栈的最小值。将第一个入栈的元素赋值给最小值变量。之后在每次进行入栈操作时，判断最小值变量与新入栈元素的大小。如果新入栈元素小于最小值变量，则修改最小值变量的值为新入栈元素。

这样我们就实现了一个栈，并且还会有一个变量指向栈的最小值。

不过遗憾的是，这个思路是错误的。因为当我们进行出栈操作的时候，如果最小值出栈了，那所声明的最小值变量就没有意义了。

所以我们在最小值出栈的时候，需要有更换顶替当前最小值的次最小值。

2.2 正确思路

上面说了，我们在最小值出栈时，需要有更换顶替当前最小值的值。我们可以通过两个栈来实现，第一个栈用于存放入栈的元素，第二个栈用于存放最小元素。

具体思路如下：

  1. 创建两个栈分别为A和B，A用于存放入栈的元素，B用于存放最小值在A中的下标或索引。
  2. 当第一个元素入A栈时，同时将其索引值推入B栈。
  3. 之后每个元素入栈A栈时，都将其与B栈栈顶的索引值对应的元素值比较，如果大于等于该元素，则忽略，如果小于该元素则入栈B。
  4. 这时，B栈的栈顶元素即为栈A的最小元素的索引。
  5. 每次元素出A栈时，如果出栈的元素的索引值等于B栈的栈顶元素，则将B栈的栈顶元素也出栈。出栈后，B栈顶的元素就会顶替出栈的最小值。

注意：B栈中之所以存索引，是因为这样可以规避一些问题。如当后加入的值和最小值相同时，如果我们不重复入栈B，那么出栈的时候对于B栈的判断就可能出问题（后入的等值元素可能会导致最小值提前出栈）。存索引就可以避免重复入栈最小值这个问题，节省一定的空间。

3. 算法实现

为了便于展示，笔者使用Vue实现了这一算法。详情可以参见https://jsbin.com/lokedoxere。实现效果如下图：

算法逻辑如下：

// 下述代码使用Vue实现，只是其中的部分
data: function () {
  return {
    // ...
    minIndeices: [],
    stack: [],
  }
},
methods: {
  // 获取最小值
  getMin: function() {
    const lastMinIndex = this.minIndeices[this.minIndeices.length - 1]
    return this.stack[lastMinIndex]
  },
  // 出栈
  pop: function () {
    const len = this.stack.length

    if(len === 0) return
    
    const lastMinIndex = this.minIndeices[this.minIndeices.length - 1]
    
    // 如果栈顶的最小值索引等于原始栈的长度 - 1，
    // 即出栈的元素为最小值，则最小值索引栈也出栈
    if(lastMinIndex === len - 1) {
      this.minIndeices.pop()
    }
      
    this.stack.pop()    
  },
  // 入栈
  push: function () {
    if(this.number === undefined) return 
    const len = this.stack.length
    
    // 如果栈为空，即添加的元素为第一个，存入第一个最小值索引
    if(len === 0) {
      this.minIndeices.push(len)
    } else {
      const currMin = this.getMin()
      if(this.number < currMin) {
        this.minIndeices.push(len)
      }
    }
    
    this.stack.push(this.number)
    this.number = undefined
  },
}

至此，我们实现了最小栈的逻辑。其实最小队列的实现思路与最小栈类似。不过又略有点不同。下面我们一起来看看吧。

二、最小队列的实现

1. 什么是最小队列

实现一个队列，带有出队（deQueue），入队（enQueue），取最小元素（getMin）三个方法。要保证这三个方法的时间复杂度都尽可能小。

2. 设计思路

这里我就不卖关子了，直接进入正题。

我们可以通过两个队列实现，第一个队列用于存放入队的元素，第二个队列用于存放最小值。

详细思路如下：

  1. 创建两个队列分别为A和B，A用于存放入队的元素，B用于存放最小值（严格来说，B不能称作队列，它会将后入的元素删除）。
  2. 当第一个元素入队A时，同时将其入队B，因为这是就唯一一个值，所以是最小值。
  3. 之后每个元素入队A时，从B队尾开始比较，如果当前值大于等于（要有等于）B队尾值，则入栈；否则，则删除B队尾值；然后再次比对B队尾值和当前值大小，直到当前值大于等于（要有等于） B队尾值或B为空，则当前值入队B尾。
  4. 这时每次B队中队首元素即为最小值。
  5. 当A中的元素出队时，如果元素值刚好与B队首元素相等，则B队首的元素也出队。（第三步中包含等于的判断，就是为了避免出队时等值元素不会出问题。）
  6. 这时deQueue/getMin时间复杂度为O(1)。enQueue为O(n)。

注意：不能像最小栈那样存索引，因为队列中的值的索引会变。所以重复的最小值要多次加入B。

3. 算法实现

同样，笔者使用Vue实现了这一算法。详情可以参见https://jsbin.com/genigakudu。实现效果如下图：

算法逻辑如下：

data: function () {
  return {
    // ...
    minQueue: [],
    queue: [],
  }
},
methods: {
  // 获取最小值
  getMin: function() {
    return this.minQueue[0]
  },
  // 出队
  deQueue: function() {
    const deNum = this.queue.shift()
    if(deNum === this.minQueue[0]) this.minQueue.shift()
  },
  // 入队
  enQueue: function () {
    if(this.number === undefined) return 
    const len = this.queue.length
    
    // 如果队列为空，即添加的元素为第一个，存入第一个最小值
    if(len === 0) {
      this.minQueue.push(this.number)
    } else {
      // 设计思路中描述的结果可以看出最小值队列是一个逐渐递增的过程，可以多添加几个试一试。
      // 所以每次有新的值入队时，可以先过滤出小于等于当前入队值的元素，然后将当前值入队。
      // 当然这样的效率并没有上面思路描述中的方式节省时间，不过时间复杂度是一样的。大家可以用常规的for循环来处理这一过程。
      this.minQueue = this.minQueue.filter(item => item <= this.number)
      this.minQueue.push(this.number)
    }
    
    this.queue.push(this.number)
    this.number = undefined
  },
}

引申

上面我们介绍并实现了最小栈和最小队列，其实大家也可以用类似的方法实现出最大栈和最大队列。如果大家有兴趣就自己动手试试吧。