LeetCode--85. 最大矩形（java）

思路：遍历每一行，生成 heights 数组，调用第84题的函数，求解每一行的最大面积即可。（效率不高）

class Solution {
    public int maximalRectangle(char[][] matrix) {
		if(matrix == null || matrix.length == 0) return 0;
		int res = 0;
		for(int i = 0;i < matrix.length;i++) {
			int[] heights = new int[matrix[0].length];
			for(int j = 0;j < heights.length;j++) {
				if(matrix[i][j] - '0' == 1) {
					for(int row = i;row >= 0;row--) {
						if(matrix[row][j] - '0' == 1) {
							heights[j]++;
						}else {
							break;
						}
					}
				}
			}
			int curArea = largestRectangleArea(heights);
			res = Math.max(curArea, res);
		}
		return res;
    }
	//84题的解
	public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i = 0;i < heights.length;i++){
            while(stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
                int cur = heights[stack.pop()] * (i - stack.peek() - 1);
                maxArea = Math.max(maxArea, cur);
            }
            stack.push(i);
        }
        while(stack.peek() != -1){
            int cur = heights[stack.pop()] * (heights.length - stack.peek() - 1);
            maxArea = Math.max(maxArea, cur);
        }
        return maxArea;
    }
}