155. 最小栈

题意：

解题思路：

思路：
1. 定义一个数据栈，存每次push、pop、top操作；
2. 再定义一个辅助栈，每次入栈元素跟辅助栈top元素比较下，如果比辅助栈栈顶元素小则入栈，大的话继续存辅助栈top元素；

图示：

PHP代码实现：

class MinStack {
    /**
     * initialize your data structure here.
     */
    private $top = -1;
    private $stack = [];
    private $minStack = [];
    function __construct() {
        $this->stack = [];
        $this->minStack = [];
    }
    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        if ($this->top == -1) {
            array_push($this->stack, $x);
            array_push($this->minStack, $x);
            $this->top++;
            return true;
        }
        $min = $this->minStack[$this->top];
        $newMin = $x < $min ? $x : $min;
        array_push($this->stack, $x);
        array_push($this->minStack, $newMin);
        $this->top++;
        return true;
    }
    /**
     * @return NULL
     */
    function pop() {
        if ($this->top == -1) return false;
        array_pop($this->minStack);
        $this->top--;
        array_pop($this->stack);
    }
    /**
     * @return Integer
     */
    function top() {
        return $this->stack[$this->top];
    }
    /**
     * @return Integer
     */
    function getMin() {
        return $this->minStack[$this->top];
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * $obj = MinStack();
 * $obj->push($x);
 * $obj->pop();
 * $ret_3 = $obj->top();
 * $ret_4 = $obj->getMin();
 */

GO代码实现：

type MinStack struct {
    sk [] int
    minSk [] int
}
/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{}
}
func (this *MinStack) Push(x int)  {
    if len(this.sk) == 0 || x <= this.GetMin() {
        this.minSk = append(this.minSk, x)
    }
    this.sk = append(this.sk, x)
}
func (this *MinStack) Pop() {
    if this.minSk[len(this.minSk)-1] == this.Top() {
        this.minSk = this.minSk[:len(this.minSk) - 1]
    }
    this.sk = this.sk[:len(this.sk) - 1]
}
func (this *MinStack) Top() int {
    return this.sk[len(this.sk) - 1]
}
func (this *MinStack) GetMin() int {
    return this.minSk[len(this.minSk)-1]
}
/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */