題目
給定一個整型矩陣map， 其中的值只有0 和 1 兩種勇吊， 求其中全是1 的所有矩形區(qū)域中集峦， 最大的矩形區(qū)域為1的數(shù)量。
例如：
1 0 1 1
1 1 1 1
1 1 1 0
其中每辟，最大的矩形區(qū)域有6個1，所以返回6 干旧。
分析
若矩陣大小為O（MN）渠欺，則時間復(fù)雜度為O（MN）的解法為：
1.對矩陣的每一行進行切割，統(tǒng)計以當(dāng)前行為底的情況下椎眯，每個位置往上1的數(shù)量挠将。(若當(dāng)前位置為1胳岂，則統(tǒng)計從當(dāng)前位置開始向上連續(xù)1的數(shù)量；若當(dāng)前位置為0舔稀，則數(shù)量計為0）
例如map=1 0 1 1
1 1 1 1
1 1 1 0
第1行height={1乳丰，0，1内贮，1}
第2行height={2产园，1，2夜郁，2}
第3行height={3什燕，2，3竞端，0}
2.計算每一行為底的情況下屎即，最大的矩形是什么。
以height={3事富，2技俐，3，0}為例
實質(zhì)是在一個直方圖中求最大的矩形面積统台。如果能求出以每一根柱子擴展出去的最大矩形虽另，那么最大的矩形就是要求的答案。
而一根柱子可擴展的最大矩形受木桶原理約束饺谬，向左最遠擴展到第一根小于它的柱子捂刺，向右最遠擴展到第一根小于它的柱子。
像這種連續(xù)的取值募寨，取值只受前后兩端影響的情況族展，可以使用棧來實現(xiàn)。
以height={3拔鹰，4仪缸，5，4列肢，3恰画，6}為例，我們知道一根柱子的最大矩形的面積只受左右兩端影響瓷马，于是我們要求的就是每一根柱子的左右兩端位置拴还。
我們從左往右遍歷height，棧為空壓入3欧聘，此時柱子height[0] 的左端已經(jīng)確定片林，只需要確定柱子的右端。由此我們得到兩個關(guān)鍵邏輯：
1.只有當(dāng)前i位置的值heigh[i]大于當(dāng)前棧頂位置所代表的值（height[stack.peek()]，則i位置才可以壓入stack
2.如果當(dāng)前i位置的值heigh[i]小于或等于當(dāng)前棧頂位置所代表的值（height[stack.peek()]费封，則把棧中存的位置不斷彈出焕妙，直到某一個棧頂所代表的值小于height[i]，再把i位置壓入
當(dāng)height[i]小于height[stack.peek()]柱子的右端位置也確定了弓摘，這個很容易理解焚鹊。但是height[i]等于height[stack.peek()]時右端位置并沒有確定，在這種情況下韧献，height[i]與height[stack.peek()]所能擴到的左右端位置必定相同寺旺，于是我們可以將height[stack.peek()]出棧，通過height[i]來求得二者的最大面積势决。
最大矩形面積為（i-k-1)*height[j]，其中i為當(dāng)前遍歷到的height位置蓝撇，k為棧頂位置果复，j為剛出棧的柱子位置。
注意渤昌，棧為空時左端位置可以記為-1虽抄，height遍歷完時右端位置可以記為height.length。
public class MaxRecSize {
public int getMaxRecSize(int[][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int[] height = new int[map[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] > 0 ? height[j] + 1 : 0;
}
max = Math.max(max, getMaxRexSizeFromBottom(height));
}
return max;
}
public int getMaxRexSizeFromBottom(int[] height) {
if(height == null || height.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < height.length; i++) {
while (!s.isEmpty() && height[s.peek()] >= height[i]) {
int current = s.pop();
int top = s.isEmpty() ? -1 : s.peek();
max = Math.max(max, (i - top - 1) * height[current]);
}
s.push(i);
}
while (!s.isEmpty()) {
int current = s.pop();
int top = s.isEmpty() ? -1 : s.peek();
max = Math.max(max, (height.length - top - 1) * height[current]);
}
return max;
}
}
