LeetCode面试题:最大矩形

发布时间:2023-04-24 10:17:09

  1.简述:

  给定一个只包含0 和 1 、大小为 rows x cols 发现二维二进制矩阵只包括 1 最大矩形,并返回其面积。

  示例 1:

  输入:matrix = [[“1”、“0”、“1”、“0”、“0”、“0”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”、“1”

  输出:6

  说明:最大矩形如上图所示。

  示例 2:

  输入:matrix = []

  输出:0

  示例 3:

  输入:matrix = [[["0]]]

  输出:0

  示例 4:

  输入:matrix = [[[[1]]]

  输出:1

  示例 5:

  输入:matrix = [[“0”,“0”]]

  输出:0

  2.实现代码:class Solution { public int maximalRectangle(char[][] matrix) { int m = matrix.length; if (m == 0) { return 0; } int n = matrix[0].length; int[][] left = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '1') { left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1; } } } int ret = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '0') { continue; } int width = left[i][j]; int area = width; for (int k = i - 1; k >= 0; k--) { width = Math.min(width, left[k][j]); area = Math.max(area, (i - k + 1) * width); } ret = Math.max(ret, area); } } return ret; }}

上一篇 定时任务系统
下一篇 LeetCode程序员面试金典:在排序数组中查找元素的第一个和最后一个位置

文章素材均来源于网络,如有侵权,请联系管理员删除。

标签: Java教程Java基础Java编程技巧面试题Java面试题