求最大子矩陣及兩種思路-資料下載頁(yè)
2025-08-23 06:16本頁(yè)面
【正文】 擴(kuò)展的最遠(yuǎn)距離了。因?yàn)槊總€(gè)位置最多被后面的位置合并一次，因此這個(gè)算法的時(shí)間復(fù)雜度為O(N)?；氐皆瓎栴}，下面來(lái)看看如何求極大化矩形。枚舉原矩形的每一行，首先更新h[i]，這里的h[i]表示第i列從當(dāng)前行往上數(shù)有多少格連續(xù)沒有被損壞的格子（直到上邊界為止）。顯然，這里的h[i]和子問題中的h[i]相同。因此利用處理子問題的方法，求出l[i]和r[i]，接著根據(jù)l[i]和r[i]，對(duì)于當(dāng)前行的每一個(gè)位置k，有長(zhǎng)為r[k]l[k]+1，寬為h[k]的符合題設(shè)要求的矩形，并且這個(gè)矩形就是極大化矩形，算法一中的預(yù)處理方法，可求出這個(gè)矩形中月餅數(shù)目。下面來(lái)分析一下時(shí)間復(fù)雜度： 枚舉每一行，時(shí)間復(fù)雜度為O(N)，更新h[i] 為O(M)，求l[i]和r[i]為O(M)，枚舉k，為O(M)，因此，總時(shí)間復(fù)雜度為O(NM)，是一個(gè)非常優(yōu)秀的算法。思考與總結(jié)：對(duì)于這類問題往往一開始就會(huì)有一些簡(jiǎn)單的想法，雖然實(shí)際效果并不是非常好，但是其思考方法總是可以借鑒的。像本題中就由簡(jiǎn)單的枚舉出發(fā)，利用枚舉矩形這個(gè)思考方式不斷的優(yōu)化，從而得到一個(gè)優(yōu)秀的算法。像這類問題的還有：Zoj2069 white rectanglesZoj1985 largest rectangle in a histogram等
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1