221. Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
S: DP O(n^2)
len[i][j]存储以i,j为右下角的全是1的max squre的边长，如果matrix[i][j] = ‘1' 那么len[i][j]等于len[i-1][j-1], len[i-1][j], len[i][j-1]三者最小值加一
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
int maxLen = 0;
vector<vector<int>> len(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == '1') {
len[i][0] = matrix[i][0];
}
maxLen = max(0, len[i][0]);
}
for (int i = 0; i < n; ++i) {
if (matrix[0][i] == '1') {
len[0][i] = matrix[0][i];
}
maxLen = max(len[0][i], 0);
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == '1') {
len[i][j] = min(len[i - 1][j - 1], len[i][j - 1]);
len[i][j] = min(len[i][j], len[i - 1][j]);
len[i][j]++;
maxLen = max(maxLen, len[i][j]);
}
}
}
return maxLen*maxLen;
}
由于len[i][j]的值只与其前一行和本行的数值有关，可以不用存储整个matrix而用滚动数组进行优化
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
int maxLen = 0;
vector<vector<int>> len(2, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
if (matrix[0][i] == '1') {
len[0][i] = 1;
maxLen = max(len[0][i], 0);
}
}
for (int i = 1; i < m; ++i) {
len[i%2][0] = matrix[i][0] - '0';
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
len[i%2][j] = min(len[(i-1)%2][j-1], len[i%2][j-1]);
len[i%2][j] = min(len[i%2][j], len[(i-1)%2][j]) + 1;
maxLen = max(maxLen, len[i%2][j]);
} else {
len[i%2][j] = 0; //因为是滚动数组，这里需要清零
}
}
}
return maxLen*maxLen;
}
85. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
S：DP O(mn)
因为不是square, 仅用边长的DP不行，需要长宽信息。这里dp三个变量，当matrix[i][j] = 1时
- height[i][j]表示从matrix[i][j]开始往上的连续1的个数，即长方形的高度
curLeft表示第从matrix[i][j]往左第一个1的位置, left[i][j] = max(curLeft, left[i-1][j])表示以height[i][j]为高度的长方形能达到的最左闭区间
curRight表示从matrix[i][j]往右第一个0的位置, right[i][j] = min(curRight, right[i-1][j])表示以height[i][j]为高度的长方形能达到的最右开区间
[left, right)即为长方形的宽度：right - left。以height[i][j]为高度的长方形大小为height[i][j] * (right[i][j] - left[i][j])
因为left取max, right取min，left初始为0, right初始为n。从上往下逐行计算，下一行结果只与上一行有关，可用一维数组dp
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector<int> left(n);
vector<int> right(n, n);
vector<int> height(n);
int result = 0;
for (int i = 0; i < m; ++i) {
int curLeft = 0; //left boundary, first 1;
int curRight = n; //right boundary, first 0 pos after 1. [left, right)
for (int j = n - 1; j >= 0; --j) { // 从右往左计算right
if (matrix[i][j] == '1') {
right[j] = min(right[j], curRight);
} else {
right[j] = n;
curRight = j;
}
}
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
height[j]++;
left[j] = max(left[j], curLeft);
result = max(result, (right[j] - left[j]) * height[j]);
} else {
height[j] = 0;
left[j] = 0;
curLeft = j + 1;
}
}
}
return result;
}
302. Smallest Rectangle Enclosing Black Pixels
An image is represented by a binary matrix with0as a white pixel and1as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location(x, y)of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
For example, given the following image:
[
"0010",
"0110",
"0100"
]
and x = 0, y = 2,
Return 6.
S: binary search, 化二维为1维 O(mlogn + nlogm)
将1投射到x轴和y轴，以x,y为分界点向左和右分别进行binary search找到边界点
class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
int m = image.size();
if (m == 0) return 0;
int n = image[0].size();
int row1 = binarySearch(image, true, true, 0, x);
int row2 = binarySearch(image, false, true, x, m - 1);
int col1 = binarySearch(image, true, false, 0, y);
int col2 = binarySearch(image, false, false, y, n - 1);
if (row2 < row1 || col2 < col1) return 0;
return (row2 - row1 + 1) * (col2 - col1 + 1);
}
int binarySearch(vector<vector<char>>& image, bool isLower, bool isRow, int left, int right) {
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (isLower) {
if (isBlack(image, mid, isRow)) right = mid;
else left = mid;
} else {
if (isBlack(image, mid, isRow)) left = mid;
else right = mid;
}
}
if (isLower) return isBlack(image, left, isRow) ? left : right;
else return isBlack(image, right, isRow) ? right : left;
}
bool isBlack(vector<vector<char>>& image, int idx, bool isRow) {
int n = isRow? image[0].size() : image.size();
for (int i = 0; i < n; ++i) {
int x = isRow ? idx : i;
int y = isRow ? i : idx;
if(image[x][y] == '1') return true;
}
return false;
}
};