色吊丝永久性观看网站在线观看,亚洲激情欧美日本国产视频小说图片电影 ,强开小嫩苞一区二区电影,国产99久久九九精品无码免费 ,人人干人人操人人,全网三级视频在线观看,精品国产福利在线,一黄大毛片

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?最大矩形，我們先來看題面：

https://leetcode-cn.com/problems/maximal-rectangle/

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

題意

給定一個(gè)僅包含 0 和 1 、大小為 rows x cols 的二維二進(jìn)制矩陣，找出只包含 1 的最大矩形，并返回其面積。

樣例

解題

https://www.cnblogs.com/techflow/p/13359851.html

題解

還是老規(guī)矩，我們從最簡單的方法入手，一點(diǎn)點(diǎn)推導(dǎo)出最佳的思路。

暴力

首先最簡單的當(dāng)然是暴力，這題讓我們尋找一個(gè)矩形，直接尋找矩形是有點(diǎn)麻煩的。計(jì)算機(jī)程序不像人眼，可以直接獲取到圖形相關(guān)的信息，計(jì)算機(jī)不行，只能獲得單個(gè)位置的信息。所以我們讓程序直接判斷矩形是不現(xiàn)實(shí)的，但我們可以通過特征點(diǎn)來鎖定矩形，這個(gè)也是業(yè)內(nèi)常用的套路。

鎖定一個(gè)矩形的方法一般有兩種，第一種是用矩形的中心點(diǎn)和長寬來確定。這一種在各種圖像識別和目標(biāo)檢測算法當(dāng)中經(jīng)常用到，模型預(yù)測的結(jié)果就是圖像中心點(diǎn)的坐標(biāo)以及長寬的長度。

第二種方法可以通過矩形的對角線上的兩個(gè)點(diǎn)來確定，這種方法只適用于和坐標(biāo)軸平行的矩形。比如下圖當(dāng)中，無論我們知道了(x2, y2), (x3, y3)還是(x1, y1), (x4, y4)，我們都可以將這個(gè)矩形確定下來。

有了確定矩形的方法之后，我們通過暴力法來求解就簡單了。我們通過這些值來枚舉所有可能構(gòu)成的矩形，然后依次遍歷矩形中的每一個(gè)元素，來判斷它們是否全是1，如果是否的話，那么就排除，否則則用來更新答案。

這種方法固然可行，但是估算一下，差不多應(yīng)該是

的規(guī)模，顯然是我們不能接受的。

分析問題

在暴力解法當(dāng)中我們遇到了時(shí)間復(fù)雜度的困難，我們想要優(yōu)化就必須要解決復(fù)雜度的問題，復(fù)雜度的問題怎么解決呢？干想肯定是不行的，我們需要轉(zhuǎn)變一下思路，尋找一下突破口。

我們枚舉的復(fù)雜度規(guī)模這么高是因?yàn)槲覀?strong style="color: rgb(71, 193, 168);">遍歷了所有矩形，遍歷矩形本身就是一個(gè)時(shí)間復(fù)雜度開銷非常大的舉動(dòng)。如果不想遍歷矩形，還有什么方法可以得出最大面積呢？如果我們聯(lián)想一下上一題很容易得出答案。

在上一題84題當(dāng)中，題目給出的是一個(gè)個(gè)豎直類型的矩形，要求這些矩形組合當(dāng)中能夠找到的最大面積。

在這題當(dāng)中我們可以對01的數(shù)字矩陣也做這么一個(gè)類似的變形，將從底部開始連續(xù)延伸的1的數(shù)量看成是豎直擺放的矩形的高度，這樣我們這題就可以使用上一題的思路進(jìn)行求解了。

["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]

比如說上面這個(gè)矩陣就可以轉(zhuǎn)變?yōu)閇4, 0, 0, 3, 0]，其實(shí)就是我們一列一列看，從最低處往上連續(xù)的1的數(shù)量。但是這樣找到的面積最大值是4，并不是答案的6，原因是因?yàn)槲覀儗ふ业牡讓硬粚Γ⒉灰欢ㄒ宰詈笠恍凶鳛榈酌娴玫降拿娣e最大。所以我們需要遍歷作為底層的行，然后用這種方法尋找最大面積，全局當(dāng)中找到的最大面積就是答案。

在上一題我們計(jì)算矩形面積的時(shí)候用到了兩個(gè)單調(diào)棧，分別計(jì)算了某一個(gè)高度向左、向右能夠延伸到的最遠(yuǎn)距離，其實(shí)這并沒有必要。因?yàn)槲覀?strong style="color: rgb(71, 193, 168);">用一個(gè)棧也可以同時(shí)計(jì)算出兩邊的邊界。舉個(gè)例子：[1, 3, 6, 7]，當(dāng)前元素是5。我們需要把6，7出棧，5入棧。我們知道了5的左邊界是3，但仔細(xì)想一想，對于7來說，我們知道了它的左右邊界。7的左邊界是6，右邊界是5。也就是說對于棧頂?shù)脑囟裕淖筮吔缡莝tack[top-1]，右邊界是當(dāng)前的位置i，寬就是i - stack[top-1] - 1。

class Solution:
????def maximalRectangle(self, matrix: List[List[str]]) -> int:
????????# 求出行數(shù)n和列數(shù)m
????????n = len(matrix)
????????if?n == 0:
????????????return?0

????????m?= len(matrix[0])
??# 存儲(chǔ)每一層的高度
????????height = [0?for?_ in range(m+1)]
????????res?= 0
????????# 遍歷以哪一層作為底層
????????for?i in range(n):
????????????sk = [-1]
????????????for?j?in range(m+1):
????????????????# 計(jì)算j位置的高度，如果遇到0則置為0，否則遞增
????????????????h = 0?if?j?== m?or?matrix[i][j] == '0'?else?height[j] + 1
????????????????height[j] = h
????????????????# 單調(diào)棧維護(hù)長度
????????????????while?len(sk) > 1?and?h < height[sk[-1]]:
????????????????????res?= max(res, (j-sk[-2]-1) * height[sk[-1]])
????????????????????sk.pop()
????????????????sk.append(j)
????????return?res

總結(jié)

乍一看這道題好像非常復(fù)雜，但是當(dāng)我們對它進(jìn)行分析和變形之后，它又變回了普通的單調(diào)棧的應(yīng)用題。在單調(diào)棧的使用當(dāng)中，有兩個(gè)細(xì)節(jié)，一個(gè)細(xì)節(jié)是棧在初始化的時(shí)候插入了-1，插入-1是作為一個(gè)標(biāo)兵，也就是所有情況能夠達(dá)到的最左側(cè)的邊界。另一個(gè)細(xì)節(jié)是維護(hù)結(jié)束的時(shí)候插入了0，插入0的目的是為了彈出棧內(nèi)所有的元素，因?yàn)橹挥谐鰲５脑貢?huì)計(jì)算構(gòu)成的面積，這樣可以保證不會(huì)遺漏情況。

除了上面提到的之外，還有其他的一些細(xì)節(jié)，比如數(shù)組的創(chuàng)建的長度，還有矩形面積的計(jì)算公式等等。很多時(shí)候算法之所以難以實(shí)現(xiàn)，也正是因?yàn)樾枰紤]的細(xì)節(jié)很多，整體的邏輯不是非常清楚，需要我們進(jìn)行大量的思考。總體來說，這是一道非常優(yōu)秀的問題，值得大家仔細(xì)鉆研。

好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。

上期推文：

LeetCode50-80題匯總，速度收藏！

LeetCode刷題實(shí)戰(zhàn)81：搜索旋轉(zhuǎn)排序數(shù)組 II

LeetCode刷題實(shí)戰(zhàn)82：刪除排序鏈表中的重復(fù)元素 II

LeetCode刷題實(shí)戰(zhàn)83：刪除排序鏈表中的重復(fù)元素

LeetCode刷題實(shí)戰(zhàn)84： ?柱狀圖中最大的矩形