Javascript solution with some explaination


  • 0
    C
    /**
     * @param {number[]} heights
     * @return {number}
     */
    var largestRectangleArea = function(heights) {
      var maxarea = 0
      var stack = []
    
      /*
       * return the top of the stack, or null
       */
      Array.prototype.top = function() {
        return this.length && this[this.length - 1] || null
      }
     
      // left boundary of the entire problem is always 0
      stack.push({leftbdforthenextpoint: 0, val: 0})
    
      for (var i = 0; i < heights.length + 1; i++) {
        if (i < heights.length && heights[i] > stack.top().val) {
          // get the left boundaries here
          //
          // when the height is increasing, we push those heights
          // into the stack, so any point in the stack can have the
          // left boundary determined by the previous point in the stack
          // to calculate the maximum area
    
          stack.push({leftbdforthenextpoint: i + 1, val: heights[i]})
        } else {
          // get the right boundaries here
          //
          // let's say the current point index is i
          // when the height is decreasing, we know a right
          // boundary for point i - 1 is found (it's i)
          // combind with the last step you can get the rectangle with
          // height[i] and hence the area
    
          while (stack.top() && stack.top().val > (heights[i] || 0)) {
            var popped = stack.pop()
            var leftbdforthenextpoint = stack.top() && stack.top().leftbdforthenextpoint || 0
            maxarea = Math.max(maxarea, (i - leftbdforthenextpoint) * popped.val)
          }
          stack.push({leftbdforthenextpoint: i + 1, val: heights[i]})
        }
      }
      return maxarea
    };
    

Log in to reply
 

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