最小栈

Sep 24, 2019

题目

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

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索栈中的最小元素。
    示例：
    1
    2
    3
    4
    5
    6
    7
    8
    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、实现栈数据结构
  • 2、获取最小元素功能的时间复杂度O(1)。

题目分析

  • 1、可以使用栈数据结构，实现其出栈，入栈，获取栈顶功能，但是仅仅用一个栈，无法实现获取最小元素功能
  • 2、时间复杂度和空间复杂度
    获取最小元素功能的时间复杂度O(1) 已是最优，因此可以考虑使用空间换取时间的策略。

解决方案

       基于上述两方面分析，结合元素进栈/出栈操作，这里我们尝试采用一个辅助栈(MinStack)配合原始栈(MainStack)实现算法需要的新特性。其时间复杂度为O(1)，空间复杂度为O(n)。一个元素压入原始栈时，条件性压入辅助栈（目的是保存当前原始栈中值最小的元素）；元素弹出原始栈时，同样需要条件性弹出辅助栈的栈顶元素（目的是确保辅助栈的栈顶元素是当前原始栈中值最小的元素）。
简单说来，流程如下：

  • 元素进栈操作
    1、辅助栈MinStack为空
           元素首先压入原始栈MainStack，而后直接压入辅助栈MinStack。
    2、辅助栈MinStack非空
           元素首先压入原始栈MainStack，而后判断该元素是否需要压入辅助栈MinStack。此时分以下两种情况：
    a. 新入栈元素大于等于辅助栈栈顶元素。该元素不会被压入辅助栈。
    b. 新入栈元素小于辅助栈栈顶元素。该元素需要被压入辅助栈。
      此处有一个细节需要注意：入栈操作过程中及完成后，辅助栈中元素自底向上是一个递减序列。
    具体分析请看下面图解(图片不再自己画图，引用网友)：
    给定一个无序整数序列： 3, 8, 5, 6, 9, 1, 0, 2
    (1) 元素3压入原始栈，此时辅助栈为空，故需要同时将其压入辅助栈。后续元素8, 5, 6, 9压入原始栈时，辅助栈不会有任何入栈操作。

(2) 元素1压入原始栈，此时辅助栈非空。元素1小于辅助栈栈顶元素3，故元素1需要同时压入辅助栈。

(3) 元素0压入原始栈，此时辅助栈亦非空。元素0小于辅助栈栈顶元素1，故元素0需要同时压入辅助栈。

       最后，尾元素2压入原始栈，因其大于辅助栈栈顶元素0，故无需压入辅助栈。至此算法的入栈操作完成。

  • 元素出栈操作
            出栈操作相对简单：首先弹出原始栈的栈顶元素，当该栈顶元素等于辅助栈的栈顶元素时，弹出辅助栈的栈顶元素，以此来保证辅助栈的栈顶元素永远是原始栈当前元素中最小的元素。

代码实现

  • Go 语言

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    type MinStack struct {
        elems []int
        mins  []int
    }

    func Constructor() MinStack {
        return MinStack{make([]int, 0), make([]int, 0)}
    }

    func (this *MinStack) Push(x int)  {
        this.elems = append(this.elems,x);
        if len(this.mins) == 0 || this.GetMin() > x {
            this.mins = append(this.mins,x);
        }
    }

    func (this *MinStack) Pop()  {
        elem := this.Top();
        this.elems = this.elems[:len(this.elems) -1]
        if elem == this.GetMin() {
             this.mins = this.mins[:len(this.mins)-1]
        }
    }

    func (this *MinStack) Top() int {
        if len(this.elems) == 0 {
            panic("empty stack")
        }
        elem := this.elems[len(this.elems)-1]
        return elem
    }

    func (this *MinStack) GetMin() int {
        if len(this.mins) == 0 {
            panic("empty stack")
        }
        elem := this.mins[len(this.mins)-1]
        return elem
    }

  • PHP 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class MinStack {
        private $mainStack;
        private $minStack;
        function __construct() {
            $this->mainStack = array();
            $this->minStack = array();
        }
      
        function push($x) {
            array_push($this->mainStack, $x);
            if(empty($this->minStack) || (!empty($this->minStack)  &&  $x < $this->minStack[count($this->minStack)-1])) {
                array_push($this->minStack,$x);
            }
            return null;
        }
      
        function pop() {
           $a =  array_pop($this->mainStack);
            if($a == $this->minStack[count($this->minStack) -1] ){
                array_pop($this->minStack);
            }
            return null;
        }
      
        function top() {
            return $this->mainStack[count($this->mainStack )-1];
        }
     
        function getMin() {
            return $this->minStack[count($this->minStack)-1];
        }
    }

    最后

          不得不说，以前落下的太多了，成为技术大大的道路太艰难，但路漫漫而修远兮，吾将上下而求索。