首页 > 作文

用PHP解决的一个栈的面试题

更新时间:2023-04-06 22:22:47 阅读: 评论:0

前言

遇到一道面试题,题目大概意思如下:

使用两个普通栈实现一个特殊栈,使中国特色社会主义理论体系的主要内容得pop、push、min三个函数的都是复杂度为o(1)的操作,min函数是获得当前栈的最小值。

初步想法

1.要实现min函数为(1)操作,当时第一想法是事先需要算好当前最小值,于是会想到用一个值来保存当前栈中最小值元素,然后push和pop操作的时候维护这个值。这样min,push都是o(1)了,但pop可不是,如果当前弹出的是最小值,需要从新寻找当前元素的最小值,这个就不是o(1)了。

2.而且上面方法没有用到另外一个栈,于是又想到:在一个栈中存储排好序的元素,同样在push和pop操作中维护这个有序堆栈,如图:

但是这样的话min操作是o(1),但是push、pop操作因为要维护这个有序栈,怎么也想不到一个方法可以o(1)的复杂度。

当时觉得肯定是在另一个栈中缓存最小值信息,但是不知道是因为没吃饭还是怎么地,思维就此僵住了。

正确解法

遇到问题解决不了,感觉心里很不爽,于是吃饭的时候又开始想怎么充分理由栈的特性,有效的缓存最小值信息,以便min操作使用。

栈操作最大的特性是只能操作栈顶元素,想到那用一个辅助栈缓存每次栈操作时的最小值,不是刚刚好。这样每次pop操作的时候,两边一起弹出就可以;因为辅助栈的栈顶元素最当前栈中的最小值,push操作是也只需要比较入栈元素和辅助栈栈顶元素就可以。这样push、pop、min都都o(1)操作了。如图:

文字可能没说清楚,上代码,下面是php的实现,通过数组来模拟堆栈。

<?php/** * 使用一个辅助栈,o(1)复杂度求出栈中的最小数 * @hack 类中通过数组来模拟堆栈 *  * @author laiwenhui */class strack{  /**   * 数据栈,存储栈数据;   *   * @var array   */  private $_arrdata = array();  /**   * 辅助栈,存储数据组栈中每层的最下值信息;   *   * @var array   */  private $_arrmin = array();  /**   * 栈顶所在单元   *   * @var int   */  private $_top=-1;  /**   * 出栈   * @return bool|int   */  public function pop(){    if ($this->_top === -1){      return fal;    }    array_pop($this->_arrmin);    $this->_top--;    return array_pop($this->_arrdata);  }  /**  邮电大学排名 * 入栈   * @param int $element   * @return二本医学院校排名 bool   */  public function push($element){    $element = intval($element);    //如果栈为空,直接入栈    if ($this->_top === -1){      array_push($this->_arrdata, $element);      array_push($this->_arrmin,daemon win7 $element);      $this->_top++;      return true;    }    //不美国农业为空,判断入栈的值是否比最小栈栈顶小    $min = $this->_arrmin[$this->_top];    //比较求出最小值    $currentmin = $element < $min ? $element : $min;    //当前栈中最小值入栈    array_push($this->_arrmin, $currentmin);    //数据入栈    array_push($this->_arrdata, $element);    $this->_top++;    return true;  }  /**   * 求当前栈空间的最小值   * @return bool|int    */  public function min(){    if ($this->_top === -1){      return fal;    }    return $this->_arrmin[$this->_top];  }}

使用如下:

复制代码 代码如下:

$obj = new strack();

$obj->push(12);

$obj->push(56);

$obj->push(23);

$obj->push(89);

$obj->push(4);

var_dump($obj->min());

$obj->pop();

var_dump($obj->min());

$obj->push(8);

var_dump($obj->min());

输出为:

复制代码 代码如下:

int(4)

int(12)

int(8)

ok,满足要求。

你是否有其他更好方法实现,如果有,请告诉我^_^

本文发布于:2023-04-06 22:22:46,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/zuowen/f48fd6b4dd5f5a52257fbdd11dc66023.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:用PHP解决的一个栈的面试题.doc

本文 PDF 下载地址:用PHP解决的一个栈的面试题.pdf

标签:最小值   操作   元素   求出
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图