004.柱状图中最大的矩形

• 84.柱状图中最大的矩形
  • 双指针 （超时）
    • 时间复杂度：O(n^2)
    • 空间复杂度：O(1)
  • 动态规划
    • 时间复杂度：O(n)
    • 空间复杂度：O(n)
  • 单调栈
    • 时间复杂度：O(n)
    • 空间复杂度：O(n)
• 11.盛最多水的容器
  • 双指针

双指针

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

动态规划

func largestRectangleArea(heights []int) int {
	n := len(heights)
	res := 0
	if n == 0 {
		return res
	}
	// leftLess: 左边第一个小于当前元素的元素索引
	leftLess := make([]int, n)
	leftLess[0] = -1
	for i := 1; i < n; i++ {
		t := i - 1
		for t >= 0 && heights[t] >= heights[i] {
			t = leftLess[t]
		}
		leftLess[i] = t
	}
 
	rightLess := make([]int, n)
	rightLess[n - 1] = n
	for i := n - 2; i >= 0; i-- {
		t := i + 1
		for t < n && heights[t] >= heights[i] {
			t = rightLess[t]
		}
		rightLess[i] = t
	}
 
	for i := 0; i < n; i++ {
		res = max(res, heights[i] * (rightLess[i] - leftLess[i] - 1))
	}
 
	return res
}

单调栈

• 接雨水：要找每个柱子左右两边第一个大于该柱子的柱子
• 本题：要找每个柱子左右两边第一个小于该柱子的柱子

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