Given a N×M binary matrix. Please output the size of second large rectangle containing all "1".
思路
一行一行地去找直方图中最大矩形(直方图最大矩形).
考察直方图中找最大矩形的过程,我们发现实际上我们可以得到对于任意块(i,j),底边包含这个块的最大矩形的形状和位置.所以对于所有块(i,j),我们找到底边包含它的最大矩形,得到一个矩形集合(去重),然后再将这些矩形生成的至多2个次小矩形(将原矩形长或宽减少1得到一个由它生成的次小矩形)也加入集合,取整个集合中第二个元素即是答案.
找直方图中最大矩形的时间复杂度是O(M),总复杂度是O(NM).
直方图中最大矩形
初始的想法是,从左到右枚举矩形的右下角块,然后对于每个右下角,快速地找到一个对于它来说最优的左上角.
这就需要一个单调栈,扫描到第k个点时,k之前的候选点的高度一定是单调增的.
但就算是高度单调增,想要找到最优的左上角也需要一个一个扫一遍.太慢.其实我们不必找到对于点k的最佳左上角,因为如果点k+1的高度大于或等于栈顶元素的高度,那最大矩形肯定不是以点k为右下角,当且仅当h[k+1]<h[k]时,我们才考虑k可能是最大矩形的右下角,然后去找一个最优的左上角.找这个左上角就从栈顶一个一个往下看,直到第一个x使得h[x]<=h[k+1],因为再往后不可能是最优解了,并且看过的这些栈中元素全都可以一并丢弃掉,因为这些元素的高度都>h[k+1].
网友评论