服务器之家

服务器之家 > 正文

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

时间:2020-07-15 15:37     来源/作者:PHP教程网

前言

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

使用两个普通实现一个特殊栈,使得pop、push、min三个函数的都是复杂度为O(1)的操作,min函数是获得当前栈的最小值。

初步想法

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

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

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

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

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

正确解法

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

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

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

文字可能没说清楚,上代码,下面是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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
<?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 ? $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,满足要求。

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

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
沙雕群名称大全2019精选 今年最火的微信群名沙雕有创意
沙雕群名称大全2019精选 今年最火的微信群名沙雕有创意 2019-07-07
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
返回顶部