单调栈计算最大矩形面积
题目:给定一个数组,数组中的元素代表木板的高度。请你求出相邻木板能剪出的最大矩形面积
我们以当前列向左右分别扩展查找,直到找到比当前小的第一个元素并且标记这个元素位置,矩形的面积为当前列高*宽度(当前列可以绘制最大宽度)
package rect import ( "main/stacktmp" ) // 给定一个数组,数组中的元素代表木板的高度。请你求出相邻木板能剪出的最大矩形面积 func Rect(s []int) int { if len(s) == 0 { return 0 } if len(s) == 1 { return s[0] } // TODO // 比当前右边小的index 集合 rightSmall := rightSmall(s) leftSmall := leftSmall(s) num := len(s) var rightPos, leftPos, ret int for i := 0; i < num; i++ { // 当前列右边比自己小坐标位置 if rightSmall[i] == -1 { rightPos = num } else { rightPos = rightSmall[i] } // 当前列左边比自己小坐标位置 leftPos = leftSmall[i] // fmt.Printf("i=%d,rightPos=%d,leftPos=%d \n", i, rightPos, leftPos) // 当前列 坐标范围 width := rightPos - leftPos - 1 height := s[i] // 求最大值 ret = max(ret, width*height) } return ret } // 从左向右找到比当前元素小的index 集合 func rightSmall(s []int) []int { stack := &stacktmp.StackTmp{} ans := make([]int, len(s)) for i := 0; i < len(s); i++ { for { if len(stack.Stack) == 0 { stack.Push(i) break } else { // 栈顶元素 peek := stack.Peek() // 找到右边比当前小的元素,并且记录下表位置 if s[i] < s[peek] { ans[peek] = i stack.Pop() } else { // 加入当前元素 stack.Push(i) break } } } } // 没有找到右边比当前小的元素标志为-1 for { if len(stack.Stack) != 0 { peek := stack.Peek() ans[peek] = -1 stack.Pop() } else { break } } return ans } // 从右向左找到比当前元素小的index func leftSmall(s []int) []int { stack := &stacktmp.StackTmp{} ans := make([]int, len(s)) for i := len(s) - 1; i >= 0; i-- { for { if len(stack.Stack) == 0 { stack.Push(i) break } else { // 栈顶元素 peek := stack.Peek() // 找到右边比当前小的元素,并且记录下表位置 if s[i] < s[peek] { ans[peek] = i stack.Pop() } else { // 加入当前元素 stack.Push(i) break } } } } // 没有找到右边比当前小的元素标志为-1 for { if len(stack.Stack) != 0 { peek := stack.Peek() ans[peek] = -1 stack.Pop() } else { break } } return ans } func max(ret, cur int) int { // fmt.Println(ret) if ret < cur { return cur } return ret }
调用
import ( "fmt" rect "main/rectangulatarea" "main/stacktmp" ) func main() { list := []int{2, 1, 5, 6, 2, 3} ret := rect.Rect(list) fmt.Println(ret) }
结果:
m@justin MINGW64 ~/Desktop/src/test $ go run main.go 10