LeetCode簡(jiǎn)易題解--221（Java讓你在一分鐘內(nèi)妙解一題）

題目描述：給定二維0，1串的矩陣，找出最大的正方形的只有1串的區(qū)域。
例如：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

答案為4.

解題思路：動(dòng)態(tài)規(guī)劃。
dp[i][j]是以（i，j）為右下角頂點(diǎn)的最大正方形的邊長(zhǎng)。

矩陣從左到右、從上到下進(jìn)行掃描，當(dāng)發(fā)現(xiàn)：
1. (i, j), (i-1, j), (i, j-1)三個(gè)位置都為1的時(shí)候，(i, j)這個(gè)值能夠與這個(gè)值左邊上邊的某個(gè)大小的區(qū)域組成一個(gè)矩陣。例如：

1 0 1 0 0
1 0 1 1 1
1 1 1 1

接下來(lái)掃描(2, 4)，發(fā)現(xiàn)(i, j), (i-1, j), (i, j-1)三個(gè)位置都為1，那么(i, j)這個(gè)值能夠與另外五個(gè)1構(gòu)成一個(gè)矩陣。
但是題目要求的是正方形的大小，因此還要找出dp(i-1, j-1), dp(i-1, j), dp(i, j-1)中的最小值min，這個(gè)最小值是以這三個(gè)值為右下角頂點(diǎn)的三個(gè)正方形中的最小邊長(zhǎng)，而掃描(i, j)這個(gè)值我們發(fā)現(xiàn)它能夠補(bǔ)成一個(gè)更大的矩陣，因此這個(gè)補(bǔ)上之后最小正方形的邊長(zhǎng)必定能夠增加1，因此令dp(i, j) = min + 1.
之所以要找dp(i-1, j-1), dp(i-1, j), dp(i, j-1)中的最小值，是因?yàn)檠a(bǔ)上的是一個(gè)矩陣，而矩陣的寬限制了正方形的邊長(zhǎng)。
2. (i, j), (i-1, j), (i, j-1)三個(gè)位置有一個(gè)為0時(shí)，肯定無(wú)法補(bǔ)成一個(gè)矩形,因此dp(i, j) = 0.

掃描過程中，變量res紀(jì)錄了所找到的最大的正方形的邊長(zhǎng)。

最終代碼如下：

class SoluTIon {

public：

int maximalSquare（vector《vector《char》》& matrix） {

if（matrix.size（） == 0） return 0;

int row = matrix.size（）， col = matrix［0］.size（）;

int res = 0;

vector《int》 dp（col， 0）;

// first row

for（int i = 0;i 《 col;i++） dp［i］ = matrix［0］［i］ - ‘0’;

res = max（res， *max_element（dp.begin（）， dp.end（）））;

// dp

for（int i = 1;i 《 row;i++） {

// first col

dp［0］ = matrix［i］［0］ - ‘0’;

// other cols

for（int j = 1;j 《 col;j++） {

if（matrix［i］［j］ == ‘1’） {

int temp = min（dp［j］， dp［j-1］）;

dp［j］ = temp + （matrix［i-temp］［j-temp］ - ‘0’）;

} else {

dp［j］ = 0;

}

}

res = max（res， *max_element（dp.begin（）， dp.end（）））;

}

return res * res;

}

};