85. 最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]
]
输出: 6
分析：
- 暴力方法，用对角确定矩阵，(a,b),(c,d),时间复杂度O(M^3 * N^3)
- 使用柱状图的暴力方法，也算一种dp,先横向累计连续的数，再纵向找连续的数字中的最小值(即矩阵宽度),用高度(连续个数)*宽度，即为当前矩阵大小，记录最大值，时间复杂度，横向扫描O(NM),纵向计算矩阵，计算完一列需要O(N^2),因为宽度min需要逐次从上边计算到下边，计算完整个，需要，O( N^2 * M)，所以时间复杂度max(O(N^2 * M),O(NM))=O(N^2*M)
- 使用栈记录柱状图的高度，非递减push,递减时，弹出，并在弹出的过程中，计算矩阵的面积，先找高度，栈中的数据是递增的，所以出栈后高度递减，即是min过程，宽度，是当前元素和次栈顶之间的元素个数，最后面积为stack.pop()*(i-stack.top()-1),注意最后需要处理未清空的栈。处理一列，每个元素入栈一次，时间复杂度O(N),M行，所以时间复杂度O(N*M)。
- dp，通过确定矩阵的W、H确定，每个矩阵的1确定其l,r,h,用三个一维数组left[w],right[w],height[w]分别表示一行中每个元素的l,r,h；其中h直接累加，遇到0，清零；类似的取l,r,并比较上一行中的l,r,取最小值,这就利用到了dp的思路，记录下来；另外，我们发现，如果用max{curLeft,left[j]},min{curRight,right[j]},那岂不是w越来越窄吗？比如(2,2)的w=1,而其所属最大矩阵面积为6，是不是我们得套用两层循环，实现一次从i初始计算height呢，是可以的；但是dp没有发挥作用，注意每个矩阵上边界都有’0’,那么我们给它是指left=0,right=n-1，其宽度是最大的，这样，我们就能保留该矩阵的curLeft和curRight，便可得到最大矩阵，具体见代码。时间复杂度O(MN)。
柱状图类型的题目还有《84. 柱状图中最大的矩形》
版本1，dp,柱状图，暴力
/* 执行用时 :36 ms, 在所有 Go 提交中击败了14.71%的用户 内存消耗 :4.5 MB, 在所有 Go 提交中击败了60.00%的用户 */
import ("fmt""math"
)
func maximalRectangleHelper(dp [][]int)int{
if len(dp)==0{
return 0}//纵向求矩阵max:=0for j:=0;j<len(dp[0]);j++{
for i:=0;i<len(dp);i++{
min,curMax,h:=math.MaxInt64,0,0for k:=i;k<len(dp);k++{
if dp[k][j]==0{
h=0}else {
h++if dp[k][j]<min{
min=dp[k][j]}curMax=h*minif curMax>max{
max=curMax}}}}}return max
}
//柱状图
func maximalRectangle(matrix [][]byte) int {
mx:=make([][]int,len(matrix))for i:=0;i<len(matrix);i++{
add:=0mx[i]=make([]int,len(matrix[i]))for j:=0;j<len(matrix[i]);j++{
if matrix[i][j]=='0'{
add=0}else{
add+=int(matrix[i][j]-'0')}mx[i][j]=add}}return maximalRectangleHelper(mx)
}
func main() {
matrix:=make([][]byte,6)matrix[0]=append(matrix[0],'1','0','1','1','0','1')matrix[1]=append(matrix[1],'1','1','1','1','1','1')matrix[2]=append(matrix[2],'0','1','1','0','1','1')matrix[3]=append(matrix[3],'1','1','1','0','1','0')matrix[4]=append(matrix[4],'0','1','1','1','1','1')matrix[5]=append(matrix[5],'1','1','0','1','1','1')fmt.Println(maximalRectangle(matrix)) //8
}
版本2，dp+栈，柱状图
/* 执行用时 :8 ms, 在所有 Go 提交中击败了64.71%的用户 内存消耗 :4.3 MB, 在所有 Go 提交中击败了60.00%的用户 */
package main
import ("fmt""math"
)
type stack struct{
v []int
}
func (stk*stack)push(v int){
stk.v=append(stk.v,v)
}
func (stk*stack)pop()int{
if len(stk.v)==0{
return -1}t:=stk.v[len(stk.v)-1]stk.v=stk.v[:len(stk.v)-1]return t
}
func (stk*stack)size()int{
return len(stk.v)
}
func (stk*stack)top()int{
if stk.size()>0{
return stk.v[len(stk.v)-1]}else{
return -1}
}func maximalRectangleHelperStack(dp [][]int)int{
if len(dp)==0{
return 0}//纵向求矩阵var stk stackstk.push(-1)//stop flagmax,curMax:=0,0for j:=0;j<len(dp[0]);j++{
for i:=0;i<len(dp);i++{
//when decliningfor stk.top()>=0&&dp[i][j]<=dp[stk.top()][j] {
curMax=dp[stk.pop()][j]*(i-stk.top()-1)if curMax>max{
max=curMax}}stk.push(i)}//tailfor stk.top()>=0{
curMax=dp[stk.pop()][j]*(len(dp)-stk.top()-1)if curMax>max{
max=curMax}}}return max
}
func maximalRectangle(matrix [][]byte) int {
mx:=make([][]int,len(matrix))for i:=0;i<len(matrix);i++{
add:=0mx[i]=make([]int,len(matrix[i]))for j:=0;j<len(matrix[i]);j++{
if matrix[i][j]=='0'{
add=0}else{
add+=int(matrix[i][j]-'0')}mx[i][j]=add}}return maximalRectangleHelperStack(mx)
}
func main() {
matrix:=make([][]byte,6)matrix[0]=append(matrix[0],'1','0','1','1','0','1')matrix[1]=append(matrix[1],'1','1','1','1','1','1')matrix[2]=append(matrix[2],'0','1','1','0','1','1')matrix[3]=append(matrix[3],'1','1','1','0','1','0')matrix[4]=append(matrix[4],'0','1','1','1','1','1')matrix[5]=append(matrix[5],'1','1','0','1','1','1')fmt.Println(maximalRectangle(matrix)) //8
}
版本3，dp,从一个点，向外探索w,h,通过dp获取(i,j)的w_min,h，这里w的获取通过l和r的获取到，之所以一次遍历可以，是因为每个矩阵上必有0位置，而0的位置，l=0,r=n-1,这样curLeft和curRight就能够保留下来，用于计算。
package main
import ("fmt""math"
)
执行用时 :8 ms, 在所有 Go 提交中击败了64.71%的用户
内存消耗 :3.4 MB, 在所有 Go 提交中击败了80.00%的用户
*/
func maximalRectangle(matrix [][]byte) int {
if len(matrix)==0{
return 0}height:=make([]int,len(matrix[0]))left:=make([]int,len(matrix[0]))right:=make([]int,len(matrix[0]))for i:=0;i<len(right);i++{
right[i]=len(matrix[0])-1}max:=0for i:=0;i<len(matrix);i++{
//update heightfor j:=0;j<len(matrix[i]);j++{
if matrix[i][j]=='0'{
height[j]=0}else{
height[j]+=1}}//update leftcurLeft:=0for j:=0;j<len(matrix[i]);j++{
if matrix[i][j]=='0'{
curLeft=j+1left[j]=0}else{
if left[j]<curLeft{
left[j]=curLeft}}}//update rightcurRight:=len(matrix[i])-1for j:=len(matrix[i])-1;j>=0;j--{
if matrix[i][j]=='0'{
curRight=j-1right[j]=len(matrix[i])-1}else{
if right[j]>curRight{
right[j]=curRight}}}//matrix areafor j:=0;j<len(matrix[i]);j++{
if matrix[i][j]=='0'{
continue}curMax:=(right[j]-left[j]+1)*height[j]if curMax>max{
max=curMax}}}return max
}
func main() {
matrix:=make([][]byte,6)matrix[0]=append(matrix[0],'0','1','1','0','1',)matrix[1]=append(matrix[1],'1','1','0','1','0',)matrix[2]=append(matrix[2],'0','1','1','1','0',)matrix[3]=append(matrix[3],'1','1','1','1','0',)matrix[4]=append(matrix[4],'1','1','1','1','1',)matrix[5]=append(matrix[5],'0','0','0','0','0',)fmt.Println(maximalRectangle(matrix))
}