leetcode：155 最小栈

在这里插入图片描述

题目的意思是：在常数时间内获得栈中的最小值，意思是常数的话，代表一次就找到，一个栈不能解决用两个吧。（常数时间内O(1)），使用两个栈，一个普通栈，一个最小元素的栈。 核心是;minstack获取了最小的更小的，所以minstack里面的都是比第一个更小的，stack里面都是比minstack大的，偶尔有一些小的话，也会出现在minstack里面，出的时候栈顶先出的话，出完了就就行了。 问题？ 为什么要出完，。，就可以保证栈顶元素是stack的最小元素了.

/**
 * initialize your data structure here.
 */
var MinStack = function() {
this.stack=[];
 this.MinStack=[];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    if(this.MinStack.length==0||x<=this.MinStack[this.MinStack.length-1])
    {
        this.MinStack.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if(this.stack.pop()==this.MinStack[this.MinStack.length-1])
    {
        this.MinStack.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.MinStack[this.MinStack.length-1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

思路:利用一个辅助栈，用来存放或者获取stack中的最小值. 开始（push）方法： 第一次数字进来的时候，先存到两个栈中，为什么？ 因为没有值怎么比较。 叼砖问题？ 为什么this.MinStack.push(x);不和 this.stack.push(x);一样在外面呢？ 因为这是有条件的，minstack栈进数字的条件，就是必须是第一次（1）或者必须进stack的值小于minstack里面的值就可以进去了（多次）.。 问题? 进去哪里？ 进去minstack中。 解释完了. MinStack.prototype.push = function(x) { this.stack.push(x); if(this.MinStack.length0||x<=this.MinStack[this.MinStack.length-1]) { this.MinStack.push(x); } }; 还有最后一个问题就是为什么[this.MinStack.length-1])，因为栈是先进后出的啊，所以说进去了就在最后一个位置也就是length-1,一切以出去的时候为原则哈. /*====================================================*/ MinStack.prototype.pop = function() { if(this.stack.pop()==this.MinStack[this.MinStack.length-1]) { this.MinStack.pop(); } }; 因为进去已经完成了，然后到出去了，如果相等就出去，这里面有什么神秘的地方呢？ 记住，pop函数是选择最上面的哪一个出的啊，与什么？ 与minstack的最上面哪一个，进行比较是否相等，如果相等就一起出去。 为什么stack也出去了，因为在比较的时候已经出去了呀。 秘密点：如果双方都出去了，代表什么？ 代表为举个例子吧。 比如: stack:123456789 minstack:1这里是不是没有一个比minstack小啊。 那： stack:121 minstack:11 记住，是stack栈顶的1与minstack栈顶的1 pop()啊 是不是只要minstack栈顶与stack的栈顶也出去了。是不是代表:minstack中的栈顶元素始终是stack的最小值啊

MinStack.prototype.top = function() { return this.stack[this.stack.length-1]; };

/**

• @return {number} */ MinStack.prototype.getMin = function() { return this.MinStack[this.MinStack.length-1]; }; 然后是返回双方的栈顶.