题目

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:输入：heights = [2,1,5,6,2,3] 输出：10

解释：最大的矩形为图中红色区域，面积为 10

示例 2：输入： heights = [2,4] 输出： 4

提示：1 <= heights.length <=105

0 <= heights[i] <= 104

注意：本题与主站 84 题相同：

解题思路分析

1、单调栈；时间复杂度O(n)，空间复杂度O(n)

func largestRectangleArea(heights []int) int {
   n := len(heights)
   res := 0
   left := make([]int, n)
   right := make([]int, n)
   stack := make([]int, 0)
   for i := 0; i < n; i++ {
      for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
         stack = stack[:len(stack)-1]
      }
      if len(stack) == 0 {
         left[i] = -1
      } else {
         left[i] = stack[len(stack)-1]
      }
      stack = append(stack, i)
   }
   stack = make([]int, 0)
   for i := n - 1; i >= 0; i-- {
      for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
         stack = stack[:len(stack)-1]
      }
      if len(stack) == 0 {
         right[i] = n
      } else {
         right[i] = stack[len(stack)-1]
      }
      stack = append(stack, i)
   }
   for i := 0; i < n; i++ {
      res = max(res, heights[i]*(right[i]-left[i]-1))
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、单调栈；时间复杂度O(n)，空间复杂度O(n)

func largestRectangleArea(heights []int) int {
   n := len(heights)
   res := 0
   left := make([]int, n)
   right := make([]int, n)
   stack := make([]int, 0)
   for i := 0; i < n; i++ {
      right[i] = n
   }
   for i := 0; i < n; i++ {
      for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
         right[stack[len(stack)-1]] = i
         stack = stack[:len(stack)-1]
      }
      if len(stack) == 0 {
         left[i] = -1
      } else {
         left[i] = stack[len(stack)-1]
      }
      stack = append(stack, i)
   }

   for i := 0; i < n; i++ {
      res = max(res, heights[i]*(right[i]-left[i]-1))
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

3、单调栈；时间复杂度O(n)，空间复杂度O(n)

func largestRectangleArea(heights []int) int {
   heights = append([]int{0}, heights...)
   heights = append(heights, 0)
   n := len(heights)
   res := 0
   stack := make([]int, 0)
   for i := 0; i < n; i++ {
      // 递增栈
      for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
         height := heights[stack[len(stack)-1]]
         stack = stack[:len(stack)-1]
         width := i - stack[len(stack)-1] - 1
         res = max(res, height*width)
      }
      stack = append(stack, i)
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Hard题目，题目类似有
leetcode 84.柱状图中最大的矩形、
leetcode 1793.好子数组的最大分数、
leetcode 1856.子数组最小乘积的最大值