搜索
首页后端开发php教程用PHP解决的一个栈的面试题_PHP

前言

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

使用两个普通栈实现一个特殊栈,使得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的实现,通过数组来模拟堆栈。

<&#63;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 false;
    }
    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, $element);
      $this->_top++;
      return true;
    }
    //不为空,判断入栈的值是否比最小栈栈顶小
    $min = $this->_arrMin[$this->_top];
    //比较求出最小值
    $currentMin = $element < $min &#63; $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 false;
    }
    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,满足要求。

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

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
PHP与Python:了解差异PHP与Python:了解差异Apr 11, 2025 am 12:15 AM

PHP和Python各有优势,选择应基于项目需求。1.PHP适合web开发,语法简单,执行效率高。2.Python适用于数据科学和机器学习,语法简洁,库丰富。

php:死亡还是简单地适应?php:死亡还是简单地适应?Apr 11, 2025 am 12:13 AM

PHP不是在消亡,而是在不断适应和进化。1)PHP从1994年起经历多次版本迭代,适应新技术趋势。2)目前广泛应用于电子商务、内容管理系统等领域。3)PHP8引入JIT编译器等功能,提升性能和现代化。4)使用OPcache和遵循PSR-12标准可优化性能和代码质量。

PHP的未来:改编和创新PHP的未来:改编和创新Apr 11, 2025 am 12:01 AM

PHP的未来将通过适应新技术趋势和引入创新特性来实现:1)适应云计算、容器化和微服务架构,支持Docker和Kubernetes;2)引入JIT编译器和枚举类型,提升性能和数据处理效率;3)持续优化性能和推广最佳实践。

您什么时候使用特质与PHP中的抽象类或接口?您什么时候使用特质与PHP中的抽象类或接口?Apr 10, 2025 am 09:39 AM

在PHP中,trait适用于需要方法复用但不适合使用继承的情况。1)trait允许在类中复用方法,避免多重继承复杂性。2)使用trait时需注意方法冲突,可通过insteadof和as关键字解决。3)应避免过度使用trait,保持其单一职责,以优化性能和提高代码可维护性。

什么是依赖性注入容器(DIC),为什么在PHP中使用一个?什么是依赖性注入容器(DIC),为什么在PHP中使用一个?Apr 10, 2025 am 09:38 AM

依赖注入容器(DIC)是一种管理和提供对象依赖关系的工具,用于PHP项目中。DIC的主要好处包括:1.解耦,使组件独立,代码易维护和测试;2.灵活性,易替换或修改依赖关系;3.可测试性,方便注入mock对象进行单元测试。

与常规PHP阵列相比,解释SPL SplfixedArray及其性能特征。与常规PHP阵列相比,解释SPL SplfixedArray及其性能特征。Apr 10, 2025 am 09:37 AM

SplFixedArray在PHP中是一种固定大小的数组,适用于需要高性能和低内存使用量的场景。1)它在创建时需指定大小,避免动态调整带来的开销。2)基于C语言数组,直接操作内存,访问速度快。3)适合大规模数据处理和内存敏感环境,但需谨慎使用,因其大小固定。

PHP如何安全地上载文件?PHP如何安全地上载文件?Apr 10, 2025 am 09:37 AM

PHP通过$\_FILES变量处理文件上传,确保安全性的方法包括:1.检查上传错误,2.验证文件类型和大小,3.防止文件覆盖,4.移动文件到永久存储位置。

什么是无效的合并操作员(??)和无效分配运算符(?? =)?什么是无效的合并操作员(??)和无效分配运算符(?? =)?Apr 10, 2025 am 09:33 AM

JavaScript中处理空值可以使用NullCoalescingOperator(??)和NullCoalescingAssignmentOperator(??=)。1.??返回第一个非null或非undefined的操作数。2.??=将变量赋值为右操作数的值,但前提是该变量为null或undefined。这些操作符简化了代码逻辑,提高了可读性和性能。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器