Leetcode_85 Maximal Rectangle

又好久没写博客了,做了一道题写一写吧。

一道难度为hard的题目,不是很难,牺牲点时间复杂度总是能够完成的。

题目:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

分析:

用类似于动态规划的思想(但不是动态规划),把每个点的左上方最大矩形的大小计算出来,最后取一个最大值即可。

关于如何计算每个点左上方的最大矩形,有点深度优先搜索的意味:首先计算改点向左最大连续1的距离,然后逐一向上进行遍历,发现某一行的连续为1的长度不等于这个距离的话,计算此时矩形的大小;然后将这个最大距离减1,逐一向上遍历,发现某一行连续为1的长度不等于这个大小的话,计算此时矩形的大小……最后计算得到的矩形大小的最大值即可。

实质就是以该点为矩形的右下角,(向上和向左)能够成矩形有很多个,找到最大的那个。

代码:

不过总觉得循环太多了,挺耗时间的。

共有 0 条评论

Top