最大矩形

单调栈（算法流程）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型二维数组 
     * @return int整型
     */
    public int maximalRectangle (int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        // 计算每个位置包括自己在内，右边有多少个连续的1
        for(int i = 0; i < n; i++){
            for(int j = m - 2; j >= 0; j--){
                matrix[i][j] = matrix[i][j] == 1? matrix[i][j] + matrix[i][j + 1]: 0;
            }
        }
        int maxArea = 0;
        int j = 0;
        while(j < m){
            int maxHeight = 0;
            int[] heights = new int[n];
            for(int k = 0; k < n; k++){
                heights[k] = matrix[k][j];
                maxHeight = Math.max(maxHeight, heights[k]);
            }
            if(maxHeight == 0) {
                j++;
                continue;
            }
            // 来一遍直方图内的最大矩形
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
            j++;
        }
        return maxArea;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0, n = heights.length;
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                int h = heights[stack.pop()];
                int L = stack.isEmpty()? 0: stack.peek() + 1;
                maxArea = Math.max(maxArea, h*(i - L));
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int h = heights[stack.pop()];
            int L = stack.isEmpty()? 0: stack.peek() + 1;
            maxArea = Math.max(maxArea, h*(n - L));
        }
        return maxArea;
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix int整型二维数组
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int maximalRectangle(int** matrix, int matrixRowLen, int* matrixColLen ) {
    // write code here
    int heights[*matrixColLen + 2];
    int stack[*matrixColLen + 2];
    int top = -1;
    int max = 0;
    heights[0] = 0;
    heights[*matrixColLen + 1] = 0;
    for (int j = 0; j < *matrixColLen + 2; j++) {
        heights[j] = 0;
    }
    for (int i = 0; i < matrixRowLen; i++) {
        //制作直方图
        heights[0] = 0;
        heights[*matrixColLen + 1] = 0;
        for (int j = 0; j < *matrixColLen; j++) {
            if (matrix[i][j] > 0)
                heights[j + 1] += matrix[i][j];
            else
                heights[j + 1] = 0;
        }
        //计算最大矩形
        for (int j = 0; j < *matrixColLen + 2; j++) {
            while (top != -1 && heights[j] <= heights[stack[top]]) {
                if (top == 0 && j < *matrixColLen + 1)
                    break;
                // 获取栈顶元素对应的高
                int curHeight = heights[stack[top--]];
                // 栈顶元素弹出后，新的栈顶元素就是其左侧边界
                int leftIndex = stack[top];
                // 右侧边界是当前考察的索引
                int rightIndex = j;
                // 计算矩形宽度
                int curWidth = rightIndex - leftIndex - 1;

                // 计算面积
                max = curWidth * curHeight > max ? curWidth * curHeight : max;
            }
            stack[++top] = j;
        }
    }
    return max;
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @return int整型
     */
    int maximalRectangle(vector<vector<int> >& matrix) {
        // write code here
        int maxArea = 0;
        
        int m = matrix.size();
        int n = matrix[0].size();
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(matrix[i][j]){
                    if(j)
                        matrix[i][j] = matrix[i][j - 1] + 1;
                    int len = matrix[i][j];
                    int height = 1;
                    while(i - height + 1 >= 0 && matrix[i - height + 1][j]){
                        len = min(len, matrix[i - height + 1][j]);
                        maxArea = max(maxArea, len * height);
                        ++height;
                    }
                }
            }
        }
        
        return maxArea;
    }
};

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix int整型二维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60?tpId=196&tqId=39479&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        1. 构建动态规划矩阵
            设dp[i][j]表示第i行以元素matrix[i][j]结尾的连续1的个数
            状态转移方程：
                若matrix[i][j] == 0:
                    dp[i][j] = 0
                否则：
                     dp[i][j] = 1 if j == 0 else dp[i][j - 1] + 1
        2. 遍历矩阵dp，对于dp[i][j]，我们从第i行枚举到0行，不断计算以matrix[i][j]为右下角的最大矩形面积，并更新res
    复杂度：
        时间复杂度：O(mn)
        空间复杂度：O(mn)
    """

    def maximalRectangle(self, matrix):
        # write code here
        m, n = len(matrix), len(matrix[0])

        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if matrix[i][0] == 1:
                dp[i][0] = 1
        for i in range(m):
            for j in range(1, n):
                if matrix[i][j] == 1:
                    dp[i][j] = dp[i][j - 1] + 1
        # print dp

        res = 0
        for i in range(m):
            for j in range(n):
                if dp[i][j] == 0:
                    continue
                area, width = dp[i][j], dp[i][j]
                for k in range(i - 1, -1, -1):
                    width = min(width, dp[k][j])
                    area = max(area, width * (i - k + 1))
                res = max(res, area)
        return res


if __name__ == "__main__":
    sol = Solution()

    # matrix = [[1]]

    # matrix = [[1, 1], [0, 1]]

    # matrix = [[0, 0], [0, 0]]

    matrix = [[1, 0, 1, 0, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]

    res = sol.maximalRectangle(matrix)

    print res

class Solution:
    def maximalRectangle(self, matrix):
        # 预处理，使每个元素的值表示从当前位置开始向上数，连续的1的个数
        for i in range(1, len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = matrix[i - 1][j] + 1 if matrix[i][j] else matrix[i][j]
        maxRec = 0
        for line in matrix:
            for i in range(len(line)):
                # 对每个>0的元素，向左求他和左边的元素能组成的最大矩形，碰到0停止
                if line[i] > 0:
                    x = 0
                    j = i
                    minH = line[i]
                    while j >= 0 and line[j] > 0:
                        minH = min(minH, line[j])
                        x += 1
                        j -= 1
                        maxRec = max(maxRec, x * minH)
        return maxRec

class Solution:
    def maximalRectangle(self , matrix: List[List[int]]) -> int:
        # write code here

        m = len(matrix)
        if not m:
            return 0
        n = len(matrix[0])
        dp = [0]*n
        ans = 0
        for i in range(m):
            for j in range(n):
                dp[j] = 0 if matrix[i][j] == 0 else dp[j]+1
            ans = max(ans,self.compute_Area(dp))
        return ans

    def compute_Area(self,heights):
        stack = [(-1,-1)]
        H = heights+[0]
        ans = 0
        for i,h in enumerate(H):
            while stack[-1][1]>h:
                _,oh = stack.pop()
                s = (i-stack[-1][0]-1)*oh
                ans = max(ans,s)
            stack.append((i,h))
        return ans