leetcode 85 Maximal Rectangle golang

原题链接

85. Maximal Rectangle

题目概述

一个矩阵. 矩阵元素是"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,再综合计算出对应的三个消息,求得结果.