Leetcode之PHP版题目解析（155. Min Stack）

Created 7 years ago by 吴亲库里, Updated 7 years ago Revision #1 3544 views 0 likes 0 collects

2019-3-12 星期二开始吧

题目描述

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

题目示例

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

题目思路

这里的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);
    }

运行结果