O(n) beautiful JS solution, please check this


  • 0
    D
    /**
     * @param {number[]} heights
     * @return {number}
     */
    var largestRectangleArea = function(heights) {
      // 最坏情况:全部height相同,每个i进出栈各一次
      // worst case: all heights are equal and each been shift and unshift once
      heights.push(0) // 确保成为所有rect的右边界; now every rect must has a right border
      let max = 0
      const stack = [] // use shift/unshift. why? because stack[0] is better than stack[stack.length-1]
      heights.forEach((height, i) => {
        // 不变式:heights[0..i-1]中,所有已知边界的rect的面积都被计算并比较过了
        // unchanged formula: in heights[0..i-1], every known-borders rect has been calculated its area
        while (stack.length && (heights[stack[0]] > height)) {
          // 注意到:当stack中存在连续相等h的i时
          // notice: when there are sequencial i in stack that has the same heights[i]
          // 最后出栈的i能正确计算出以该h为高的rect的左边界;
          // the leftest one will lead to the correct left border of the rect that includes i
          // 最先出栈的i则可能成为右边某rect的左边界
          // the rightest one may become some rects left border
          const h = heights[stack.shift()]
          const w = stack.length ? (i - stack[0] - 1) : i
          max = Math.max(max, h * w)
        }
        stack.unshift(i)
        // 每轮过后,heights[0..i]中右边界为heights[i]的rect的面积都被计算并比较过了
        // after each turn, every rect that is in heights[0..i] and use heights[i] as its right border has been calculated its are
      })
      return max
    };
    

Log in to reply
 

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