原题链接
题目概述
一个矩阵. 矩阵元素是"0", "1"其中之一, 找到一个内部元素为"1"的最大矩阵,
解题思路
想到了84题我的博客
每一行如果都可以得到高度的话,这样这个问题就可以用之前的问题解决.
假设矩形为m * n, 即m行n列.
每一行求高度,可以由该行的值和上一轮的结果算出,算法复杂度O(n),之后算这样行为底边的矩形最大值,算法复杂度O(n),总的算法复杂度O(n), 有m行, 所以该题的算法复杂度O(m * n)
这应当是最小值了,
代码
func largestRectangleArea(heights []int) int {
var result int
result = 0
tmpResult := 0
heights = append(heights, 0)
heightIndex := make([]int, 0)
tmpValue := 0
tmpIndex := 0
for index, value := range heights {
for {
if len(heightIndex) == 0 || value >= heights[heightIndex[len(heightIndex) - 1]] {
heightIndex = append(heightIndex, index)
break
} else {
// if no pre index, you can consider the pre index is -1
if len(heightIndex) == 1 {
tmpIndex = -1
} else {
tmpIndex = heightIndex[len(heightIndex) - 2]
}
tmpValue = heights[heightIndex[len(heightIndex) - 1]]
tmpResult = (index - tmpIndex - 1) * tmpValue
if result < tmpResult {
result = tmpResult
}
heightIndex = heightIndex[:len(heightIndex) - 1]
}
}
}
heights = heights[:len(heights) - 1]
return result
}
func maximalRectangle(matrix [][]byte) int {
if len(matrix) == 0 {
return 0
}
result := 0
tmpResult := 0
tmpHeights := make([]int, len(matrix[0]))
tmpHeights
for _, heights := range matrix {
for index, value := range heights {
if value == "1" {
tmpHeights[index] += 1
} else {
tmpHeights[index] = 0
}
tmpResult = largestRectangleArea(tmpHeights)
if tmpResult > result {
result = tmpResult
}
}
}
return result
}
post
看了网上的同仁的方法,还有一个是使用动态规划做的链接.大致意思是对于某一坐标为(x,y)的元素,以之为底;尽可能地往该点上方做延伸,且以之为高;这条高尽可能的左右延伸,得到这一点的对应矩形.这样的面积算作是该点对应矩阵的面积.计作s(x,y)
因而这样是可以覆盖到最大矩阵的.
为了计算该矩阵的面积,需要知道三个信息, l(x,y):该矩形的左边界, r(x,y): 该矩形的右边界, h(x,y)该矩形的高度. s = (r - l + 1) * h
对于某一元素,如果为0,结果为0.否则首先计算只有该行的结果:l2(x), r2(x),分别为该点向左尽可能延伸的x,该点尽可能向右延伸的x. 然后通过它头顶的元素是否为0,再综合计算出对应的三个消息,求得结果.