155.md

✏️Leetcode基础刷题之(155. Min Stack)

2019-03-12 吴亲库里 库里的深夜食堂

---

✏️描述

设计一个支持push，pop，top以及在恒定时间内检索最小元素的堆栈。

---

✏️题目实例

​

✏️题目分析

这里的push就是将元素压入栈顶(PHP中的array_unshift),pop就是弹出栈顶元素(PHP中的array_shift),然后getMin()用来获取数组中最小的数.

        /**
           * initialize your data structure here.
           */
          private $data=[];
          
          function __construct() {
             
          }
        
          /**
           * @param Integer $x
           * @return NULL
           */
          function push($x) {
               array_unshift($this->data,$x);
              
          }
        
          /**
           * @return NULL
           */
          function pop() {
                array_shift($this->data);
          }
        
          /**
           * @return Integer
           */
          function top() {
                  return $this->data[0];
          }
        
          /**
           * @return Integer
           */
          function getMin() {
             return min($this->data);
          }

简单粗暴的结果就是运行效率偏低下.

---

✏️代码调整

  /**
     * initialize your data structure here.
     */
    private $data=[];
    private $min=[];
    
    function __construct() {
       
    }
  
    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
         array_unshift($this->data,$x);
        if(count($this->min)==0 || $x<=$this->getMin()) {
            array_unshift($this->min,$x);
        }
    }
  
    /**
     * @return NULL
     */
    function pop() {
          $value=array_shift($this->data);
        if(count($this->min)>0 && $value===$this->getMin()){
            array_shift($this->min);
        }
        
    }
  
    /**
     * @return Integer
     */
    function top() {
        return $this->data[0];
    }
  
    /**
     * @return Integer
     */
    function getMin() {
        return min($this->min);
    }

---

✏️优化

不管是第一版还是第二版在处理最小值的时候最后都是用的min()函数求出的,题目的要求是在恒定的时间内检索出最小元素,更优解留给你们思考吧

联系

​