双指针 §
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
}