最大01子矩陣

n*m構(gòu)成的01矩陣當(dāng)中求出最大的全1矩陣，n,m<=2e3

哈哈，想不到寫掛了，雖然知道是單調(diào)棧，但是寫了一下居然寫錯了

錯誤寫法：

for (int i = 1; i <= n; i ++){stack <node> s;for (int j = 1; j <= m; j ++){while (!s.empty() && s.top().num > dp[i][j]){ans = max (ans, s.top().num * (j - s.top().pos));s.pop();}node temp;temp.num = dp[i][j]; temp.pos = j;s.push(temp);}while (!s.empty()){ans = max (ans, s.top().num * (m + 1 - s.top().pos));s.pop();}}

很容易造出數(shù)據(jù)將其hack掉，如果一行當(dāng)中出現(xiàn)了3 2 3，那么最后的答案是4，忽略了第一個3當(dāng)中的2

糾正方法：每一次入棧的時候，找到比當(dāng)前數(shù)大的最小的一個，將其修改為當(dāng)前的數(shù)，更大的就全部pop出去

正確寫法：

for (int i = 1; i <= n; i ++){stack <int> s;dp[i][m + 1] = 0;for (int j = 1; j <= m + 1; j ++){if (s.empty() || dp[i][j] >= dp[i][s.top()])s.push(j);else{int top;while (!s.empty() && dp[i][j] < dp[i][s.top()]){top = s.top(); s.pop();ans = max(ans, ((j - top) * dp[i][top]));}s.push(top);dp[i][top] = dp[i][j];} }}

總結(jié)

以上是生活随笔為你收集整理的最大01子矩阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。