Javascript solution: ONLY one stack and no extra space required.


  • 1
    Y
    /**
     * @constructor
     */
    var MinStack = function() {
        this.values = [];
        this.minValue;
    };
    
    /**
     * @param {number} x
     * @returns {void}
     */
    MinStack.prototype.push = function(x) {
        this.values.push([x,this.minValue]);
        
        if(this.values.length === 1)
            this.minValue = x;
        else if(x < this.minValue)
            this.minValue = x;
    };
    
    /**
     * @returns {void}
     */
    MinStack.prototype.pop = function() {
        var items = this.values.pop();
        this.minValue = items[1];
    };
    
    /**
     * @returns {number}
     */
    MinStack.prototype.top = function() {
        return this.values[this.values.length - 1][0];
    };
    
    /**
     * @returns {number}
     */
    MinStack.prototype.getMin = function() {
        return this.minValue;
    };

  • 2
    H

    Every time you push two elements, so there IS actually extra space. The extra space is the same if you have another stack.


  • 0
    Y

    OK, but the questions doesn't restrict to only one stack right, the only requirement is retrieving minimum value in constant time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.