• 85. 最大矩形 java解决


    题目描述:

    难度:困难
    相关标签:栈、数组、动态规划、矩阵、单调栈
    
    给定一个仅包含0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
    
    示例 1:
    

        输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
        输出:6
        解释:最大矩形如上图所示。
    示例 2:
        输入:matrix = []
        输出:0
    示例 3:
        输入:matrix = [["0"]]
        输出:0
    示例 4:
        输入:matrix = [["1"]]
        输出:1
    示例 5:
        输入:matrix = [["0","0"]]
        输出:0
    
    提示:
        rows == matrix.length
        cols == matrix[0].length
        1 <= row, cols <= 200
        matrix[i][j] 为 '0' 或 '1'

    解题:

    1. 我们首先计算出矩阵的每个元素的左边连续 1 的数量,使用二维数组 left 记录,其中 left[i][j]        为矩阵第 i 行第 j 列元素的左边连续 1 的数量。
    2. 对于矩阵中任意一个点,我们枚举 以该点作为右下角 的全 1 矩形。

    1. class Solution {
    2. //自己写的(优化柱状暴力)
    3. public int maximalRectangle(char[][] matrix) {
    4. if( matrix == null )
    5. return 0;
    6. int x = matrix.length, y = matrix[ 0 ].length;
    7. //我们首先计算出矩阵的每个元素的左边连续 1 的数量,使用二维数组 left 记录,其中 left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量。
    8. int[][] left = new int[ x ][ y ];
    9. for ( int i = 0; i < x; i ++ ) {
    10. for ( int j = 0; j < y; j ++ ) {
    11. if( matrix[ i ][ j ] == '1' ) {
    12. left[ i ][ j ] = ( j == 0 ? 0 : left[ i ][ j - 1 ] ) + 1;
    13. }
    14. System.out.print( left[ i ][ j ] + " " );
    15. }
    16. System.out.println();
    17. }
    18. //对于矩阵中任意一个点,我们枚举 以该点作为右下角 的全 1 矩形。
    19. int max = 0;
    20. int[][] dp= new int[ x ][ y ];
    21. for ( int i = 0; i < x; i ++ ) {
    22. for ( int j = 0; j < y; j ++ ) {
    23. if( left[ i ][ j ] != 0 ) {
    24. int width = left[ i ][ j ];
    25. if ( max == 0 )
    26. max = width * 1;
    27. int high = 0, min = width;
    28. for( int a = i; a >= 0; a -- ) {
    29. high ++;
    30. min = left[ a ][ j ] <= min ? left[ a ][ j ] : min;
    31. if ( left[ a ][ j ] == 0 )
    32. break;
    33. if ( left[ a ][ j ] >= width ) {
    34. if ( width <= min )
    35. max = ( width * high ) >= max ? width * high : max;
    36. else max = ( min * high ) >= max ? min * high : max;
    37. } else if ( left[ a ][ j ] < width ) {
    38. if(left[ a ][ j ] <= min )
    39. max = left[ a ][ j ] * high >= max ? left[ a ][ j ] * high : max;
    40. else max = ( min * high ) >= max ? min * high : max;
    41. }
    42. }
    43. }
    44. }
    45. }
    46. return max;
    47. }
    48. }

  • 相关阅读:
    J2EE从入门到入土02.Set及Map集合解析
    关于如何计算 递归 方法 的时间复杂度 笔记总结
    131.分割回文串
    使用 Web HID API 在浏览器中进行HID设备交互(纯前端)
    Java--Spring之IoC控制反转;基于XML配置文件的DI
    Vue3中defineEmits、defineProps 是怎么做到不用引入就能直接用的
    js中的设计模式之适配器模式
    深度剖析集成学习Xgboost(续)
    Kakao账号注册全流程,如何Kakao多开?
    Stable Diffusion被爆包含性别、种族歧视!比AI更可怕的是人类的偏见......
  • 原文地址:https://blog.csdn.net/QRLYLETITBE/article/details/126771637