Why my js code om Min Stack is always limited runtime error?


  • 2
    C

    /**

    • @constructor
      */
      var MinStack = function() {
      this.dataStore = [];
      this.peek = 0;
      };

    /**

    • @param {number} x
    • @returns {void}
      */
      MinStack.prototype.push = function(x) {
      this.dataStore[this.peek++] = x ;
      };

    /**

    • @returns {void}
      */
      MinStack.prototype.pop = function() {
      this.dataStore[--this.peek];
      };

    /**

    • @returns {number}
      */
      MinStack.prototype.top = function() {
      return this.dataStore[this.peek-1];
      };

    /**

    • @returns {number}
      */
      MinStack.prototype.getMin = function() {
      var min = this.dataStore[0];
      var tmp;
      for(var i=1;i<=this.peek-1;i++){
      if (this.dataStore[i] < min){
      tmp = min;
      min = this.dataStore[i];
      this.dataStore[i] = tmp;
      }
      }
      return min;
      };

  • 0
    C

    /** * @constructor */ var MinStack = function() { this.dataStore = []; this.peek = 0; };

    /** * @param {number} x * @returns {void} */ MinStack.prototype.push = function(x) { this.dataStore[this.peek++] = x ; };

    /** * @returns {void} */ MinStack.prototype.pop = function() {this.dataStore.splice(--this.peek,1); };

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

    /** * @returns {number} */ MinStack.prototype.getMin = function() { var min = this.dataStore[0]; var tmp; for(var i=1;i<=this.peek-1;i++){ if (this.dataStore[i] < min){ tmp = min; min = this.dataStore[i];
    this.dataStore[i] = tmp; } } return min; };

    I have modified but the runtime error is also exist.


  • 1
    H

    I try something like this:

    
    /**
     * @constructor
     */
    var MinStack = function() {
        this.stack=[];
    };
    
    /**
     * @param {number} x
     * @returns {void}
     */
    MinStack.prototype.push = function(x) {
        this.stack.push(x);
    };
    
    /**
     * @returns {void}
     */
    MinStack.prototype.pop = function() {
       this.stack.pop();
    };
    
    /**
     * @returns {number}
     */
    MinStack.prototype.top = function() {
        return this.stack[this.stack.length-1];
    };
    
    /**
     * @returns {number}
     */
    MinStack.prototype.getMin = function() {
        return Math.min.apply(null, this.stack);
    };
    
    

    and I also get Time Limit Exceeded


  • 1
    J

    I think that it's no JavaScript solution for this problem.

    ===========================
    Update: 2015/6/25

    I sent feedback to Leetcode, and here was the response:

    I have decrease the test case size and your solution is accepted now.
    However do note that your solution is not optimal, in your getMin()
    function costs O(n). An ideal solution should cost only O(1) in getMin().

    So I changed my solution:

    /**
     * @constructor
     */
    var MinStack = function() {
        this.minStack = [];
        this.container = [];
    };
    
    /**
     * @param {number} x
     * @returns {void}
     */
    MinStack.prototype.push = function(x) {
        this.container.push(x);
        if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(x);
        }
    };
    
    /**
     * @returns {void}
     */
    MinStack.prototype.pop = function() {
        var x = this.container.pop();
        if (x === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    };
    
    /**
     * @returns {number}
     */
    MinStack.prototype.top = function() {
        return this.container[this.container.length - 1];
    };
    
    /**
     * @returns {number}
     */
    MinStack.prototype.getMin = function() {
        return this.minStack[this.minStack.length - 1];
    };

Log in to reply
 

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