leetCode ✏Leetcode基础刷题之(155. Min Stack)
✏描述
设计一个支持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()函数求出的,题目的要求是在恒定的时间内检索出最小元素,更优解留给你们思考吧
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)