-
Notifications
You must be signed in to change notification settings - Fork 17
/
stack_min_value.php
62 lines (55 loc) · 1.28 KB
/
stack_min_value.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
<?php
/**
* 剑指 Offer 系列:包含 min 函数的栈
* @author 学院君
*/
class PhpStack
{
private $_stack;
private $_min_stack;
public function __construct()
{
$this->_stack = [];
$this->_min_stack = [];
}
public function push($data)
{
array_push($this->_stack, $data);
// 维护辅助栈
if (empty($this->_min_stack)) {
array_push($this->_min_stack, $data);
} else {
$min = end($this->_min_stack);
if ($data < $min) {
array_push($this->_min_stack, $data);
} else {
array_push($this->_min_stack, $min);
}
}
}
public function pop()
{
$data = array_pop($this->_stack);
// 维护辅助栈
if (!empty($this->_min_stack)) {
$min = end($this->_min_stack);
if ($min == $data) {
array_pop($this->_min_stack);
}
}
return $data;
}
public function min()
{
return end($this->_min_stack);
}
}
// 测试代码
$nums = [3, 4, 2, 1];
$stack = new PhpStack();
foreach ($nums as $num) {
$stack->push($num);
}
var_dump($stack->min()); // 1
var_dump($stack->pop()); // 1
var_dump($stack->min()); // 2