/**
使用双队列，一个记录全部数据，一个记录最大的数字
*/
class MaxQueue {
private $maxQueue = [];
private $numQueue = [];
function __construct() {
$this->maxQueue = [];
$this->numQueue = [];
}
/**
* @return Integer
*/
function max_value() {
return $this->maxQueue[0]?$this->maxQueue[0]:-1;
}
/**
* @param Integer $value
* @return NULL
*/
function push_back($value) {
array_push($this->numQueue,$value);
while(!empty($this->maxQueue) && ($this->maxQueue[count($this->maxQueue)-1] <= $value)) {
array_pop($this->maxQueue);
}
array_push($this->maxQueue,$value);
}
/**
* @return Integer
*/
function pop_front() {
$num = array_shift($this->numQueue);
if($num == $this->maxQueue[0]){
array_shift($this->maxQueue);
}
return $num?$num:-1;
}
}
