Given a N×M binary matrix. Please output the size of second large rectangle containing all "1".
思路
一行一行地去找直方圖中最大矩形(直方圖最大矩形).
考察直方圖中找最大矩形的過程,我們發(fā)現(xiàn)實(shí)際上我們可以得到對于任意塊(i,j),底邊包含這個塊的最大矩形的形狀和位置.所以對于所有塊(i,j),我們找到底邊包含它的最大矩形,得到一個矩形集合(去重),然后再將這些矩形生成的至多2個次小矩形(將原矩形長或?qū)挏p少1得到一個由它生成的次小矩形)也加入集合,取整個集合中第二個元素即是答案.
找直方圖中最大矩形的時間復(fù)雜度是O(M),總復(fù)雜度是O(NM).
直方圖中最大矩形
初始的想法是,從左到右枚舉矩形的右下角塊,然后對于每個右下角,快速地找到一個對于它來說最優(yōu)的左上角.
這就需要一個單調(diào)棧,掃描到第k個點(diǎn)時,k之前的候選點(diǎn)的高度一定是單調(diào)增的.
但就算是高度單調(diào)增,想要找到最優(yōu)的左上角也需要一個一個掃一遍.太慢.其實(shí)我們不必找到對于點(diǎn)k的最佳左上角,因?yàn)槿绻c(diǎn)k+1的高度大于或等于棧頂元素的高度,那最大矩形肯定不是以點(diǎn)k為右下角,當(dāng)且僅當(dāng)h[k+1]<h[k]時,我們才考慮k可能是最大矩形的右下角,然后去找一個最優(yōu)的左上角.找這個左上角就從棧頂一個一個往下看,直到第一個x使得h[x]<=h[k+1],因?yàn)樵偻蟛豢赡苁亲顑?yōu)解了,并且看過的這些棧中元素全都可以一并丟棄掉,因?yàn)檫@些元素的高度都>h[k+1].
