[POJ2559POJ3494] Largest Rectangle in a HistogramLargest Submatrix of All 1’s 「單-技術動態-匯編語言學習筆記

[POJ2559POJ3494] Largest Rectangle in a HistogramLargest Submatrix of All 1’s 「單

2023-12-25 阅读 25 评论 0

摘要：Largest Rectangle in a Histogram http://poj.org/problem?id=2559 題意：給出若干寬度相同的矩形的高度（條形統計圖），求最大子矩形面積解題思路單調棧的經典題（嫌棄字多可以先看后面的示例再來看這個思路）顯然，最終

Largest Rectangle in a Histogram

http://poj.org/problem?id=2559

題意：給出若干寬度相同的矩形的高度（條形統計圖），求最大子矩形面積

解題思路

單調棧的經典題（嫌棄字多可以先看后面的示例再來看這個思路）

顯然，最終的子矩形高度一定和某一個矩形相等（反證）。因此一個暴力的做法就是枚舉每一個矩形，然后往兩邊擴散。在它左側找到第一個高度比它小的，右側也一樣。則可以求出最大可擴散寬度，乘上高度即可以更新答案。復雜度O(n2)

如果說要優化剛才的算法，也就可以優化尋找最大可擴散寬度的速度

讓每一個矩形依次入棧，保存兩個關鍵字：矩形高度，其最大左擴散寬度。保證棧內的矩形高度單調遞增

我們可以得到結論：目前棧內的一個矩形u。這就是為什么我們不需要統計棧內矩形的最大右擴散寬度，因為最大右擴散寬度就是棧頂

再回憶一下最大左擴散寬度的意義，是在它左側的高度大于它的矩形們。這讓我們又得出一個結論：目前棧內的一個矩形u。這也很容易發現，因為棧是單調遞增的。或者，我們可以得到一個更形象的結論：棧內連續的兩個矩形u,v

因此剛才我們所說的最大左擴散寬度，其實等同于在原圖中，它到棧中上一個矩形之間相隔了多少矩形

當一個新的矩形進來的時候，它會彈走若干個矩形。而棧內一個矩形實際上代表著原圖中一段矩形。因此可以說是彈走了幾段矩形。但是這些被彈走的矩形只不過出棧，在原圖中并不會消失。因此他們所代表的的寬度不應當消失，所以我們將他們累積在新進來的這個矩形上。這也非常符合事實——這個新的矩形之所以能彈走這若干個矩形是因為自己比他們矮，因此都可以擴散到。換句話說，被彈走的這一系列矩形最多只能向右擴散到這個新矩形，因此留著它們就沒有意義了

而對于任何一個要出棧的矩形，我們需要統計由它的高度所能擴散出去的最大子矩形面積。由于它的最大左擴散寬度已知，唯一需要知道的就是它的最大右擴散寬度。那么由于它在棧里，它的最大右擴散寬度也就是從它一直到最早先的棧頂之間的寬度。因此我們只需要在彈棧的過程中一路累積每個出棧矩形的最大左擴散寬度，加起來就是這一段寬度了。

另外，如果處理完了最后一個矩形以后棧依然有剩余，則應當彈完并更新答案

保證了每個矩形入棧以及出棧恰好一次，在正確性顯然的條件下，復雜度O(n)

這里給出示例，以幫助理解：

例子就用題目中的[2,1,5,6,2,3]吧

首先，如果棧是空的，那么索引i入棧。那么第一個i=0就進去吧。注意棧內保存的是索引，不是高度。然后i++。

然后繼續，當i=1的時候，發現h[i]小于了棧內的元素，于是出棧。（由此可以想到，哦，看來stack里面只存放單調遞增的索引）

這時候stack為空，所以面積的計算是h[t] * i.t是剛剛彈出的stack頂元素。也就是藍色部分的面積。

繼續。這時候stack為空了，繼續入棧。注意到只要是連續遞增的序列，我們都要keep pushing，直到我們遇到了i=4，h[i]=2小于了棧頂的元素。

這時候開始計算矩形面積。首先彈出棧頂元素，t=3。即下圖綠色部分。

接下來注意到棧頂的（索引指向的）元素還是大于當前i指向的元素，于是出棧，并繼續計算面積，桃紅色部分。

最后，棧頂的（索引指向的）元素大于了當前i指向的元素，循環繼續，入棧并推動i前進。直到我們再次遇到下降的元素，也就是我們最后人為添加的dummy元素0.

同理，我們計算棧內的面積。由于當前i是最小元素，所以所有的棧內元素都要被彈出并參與面積計算。

注意我們在計算面積的時候已經更新過了maxArea。

Code

?這里如果一下子理解不過來的話，wid可以分兩步求，wid = l + r

r = j-t; //右邊能擴散的最大寬度
l = s.empty()?t:(t-s.top()-1); //左邊能擴大的最大寬度

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;typedef long long ll;
ll h[100005];stack<int> s;int main()
{int n;while (scanf("%d", &n)&&n) {memset(h, 0, sizeof(h));  while(!s.empty()) s.pop();for (int i = 0; i < n; i++) scanf("%lld", &h[i]);ll j = 0, res = 0;while (j<=n) {if (s.empty()||h[s.top()]<=h[j])s.push(j++);else {ll t = s.top(); s.pop();ll wid = s.empty()?j:(j-s.top()-1);res = max(res, h[t]*wid);}}printf("%lld\n", res);}
}

View Code

這題算法是沒什么問題的，但是特別要注意的是，如何不單獨寫成一個函數的話，由于最后push進去了h值為0的n，這個對之后wid求值時候可能為負數就會出現問題，還有就是要保證每組數據輸入完后h[n]要為0

?Largest Submatrix of All 1’s

?http://poj.org/problem?id=3494

題意：給你一個n*m的矩陣，矩陣的每個位置值為0或者1，問你在這個矩陣中全部由1組成的最大的矩形面積為多少。
思路：很巧妙的方法。把圖拆成一行行來做，分別求以每行為底的最大矩形面積

矩陣中的子矩陣等同于序列中的子序列，只不過此題要做一個預處理，將這個矩陣分為以每一行為x軸的n個柱狀圖，對于每一個等于1的點，它的高度都等于上一行同一列的點的高度加一。

初始化后，再對n個柱狀圖進行如上題POJ2559的處理。
例如：

例子

初始化后

以第一行為 x 軸

以第二行為 x 軸

以第三行為 x 軸

Code

#include<stdio.h>
#include<stack>
using namespace std;int h[2005][2005];
stack<int> s;int main()
{int n, m;while(~scanf("%d%d",&n,&m)) {for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {scanf("%d",&h[i][j]);if(h[i][j]==1&&i>0) h[i][j]+=h[i-1][j];}}for(int i = 0; i < n; i++) h[i][m] = 0;int res = 0;for (int i = 0; i < n; i++) {while(!s.empty()) s.pop();int j = 0;while (j<=m) {if (s.empty()||h[i][s.top()]<=h[i][j])s.push(j++);else {int t = s.top(); s.pop();int wid = s.empty()?j:(j-s.top()-1);res = max(res, h[i][t]*wid);}}}printf("%d\n", res);}return 0;
}