程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode]Maximal Rectangle

[LeetCode]Maximal Rectangle

編輯:關於C++

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

動態規劃

用left[ ]數組紀錄該點距離最左邊(在矩形內部)的1的距離,用right[ ]數組紀錄該點距離最右邊(在矩形內部)的1距離,height[ ]記錄該點的矩形內1的最大高度



public class Solution {
	public int maximalRectangle(char[][] matrix) {
		if (matrix.length == 0)	return 0;
		int row = matrix.length;
		int column = matrix[0].length;
		int left[] = new int[column], right[] = new int[column], height[] = new int[column];
		Arrays.fill(right, column-1);
		int res = 0;
		for (int i = 0; i < row; i++) {
			int l = 0, r = column - 1;
			for (int j = 0; j < column; j++) {
				if (matrix[i][j] == '1') {
					left[j] = Math.max(left[j], l);
					height[j]++;
				} else {
					l = j+1;
					left[j] =0;
					height[j] = 0;
					right[j] = column - 1;
				}
			}

			for (int j = column - 1; j >= 0; j--) {
				if (matrix[i][j] == '1') {
					right[j] = Math.min(r, right[j]);
					res = Math.max(res, height[j] * (right[j] - left[j]+1));
				} else {
					r = j-1;
				}
			}
		}
		return res;
	}
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved