AIZU ONLINE JUDGEのDPL_3_B: Largest Rectangleを題材に、最大長方形を求める問題の解法をまとめます。
問題では、綺麗なタイルが0、汚れたタイルが1で与えられ、
綺麗なタイルでのみ作れる最大長方形の面積を求めます。
白を綺麗なタイル、黒を汚れたタイルとして、下図のようにタイルの情報が渡されたとします。
そして、各々の地点における最大の高さを別の配列(Tとする)に保存しておきます。
スタックを用いた最大長方形の求め方
ここでは、スタックを利用して、最大長方形を求めてみます。
四角形の面積を求めるためのクラス・構造体(rectとする)を作成し、これをスタックに入れます。
スタックにプッシュするrectは最大長方形を調べていく過程でまだ拡張される可能性のあるものになります。
最大長方形を調べるプロセスで、スタックに入っている最大長方形がこれ以上拡張されない場合、スタックにある対象のrectを取り出し、面積を計算し、最大面積を更新します。
これを繰り返すことで、最大面積を求めていきます。
具体例で最大面積を求めるプロセスを確認する
では、具体例でプロセスを確認します。
まず、rectを定義します。
rectの定義
struct Rectangle{
// indexの地点の高さ(Tに保存されている)
int height;
// stackに追加した始点のindex x
int pos;
};
heightとposを掛けることで、保存したrectの面積を求めることができるようにします。
rectをstackに保存するプロセス
長方形の最大面積を求めるために、タイルの高さを保存した2次元配列(T)を左上から右下へ走査していきます。
その配列の同じ行を左から右に操作しその行の高さ計算が終了したら、
stackを解放します。
その際、以下の条件の時にスタックを入れる対象となるrectを作成し、pushします。
スタックが空の場合
高さと位置を表すx座標をもつrectを作成して、スタックにpushします。
対象の高さがstackのトップよりも高い場合
対象となるrectを作成し、スタックにpushします。
なぜ、スタックにpushするのかというと、この位置の四角形の面積が最大面積を更新する可能性があるからです。
以下の図の5行目のケースを考えてみます。
最初の地点の高さ1、pos:0はスタックが空なので、そのまま積み上げます。
次の地点は高さが2になってます。
stackトップの高さは先ほど積み上げた1なので、この地点のrect(height:2,pos:1)もスタックに追加します。
高さが2なので、右に走査していく過程で高さが2以上のタイルがあれば、先ほど追加した高さ1のrectの面積よりも大きくなる可能性がありるので、スタックに保存する必要があります。
工程を考えるとわかるように、スタックにトップに積まれているrectの高さは最大のものになります。
対象の高さがスタックのトップよりも低い場合
対象の高さがスタックのトップよりも低い場合は、
下図のケースのようにスタックに積んであるrectが長方形でなくなってしまうため、
対象の高さよりも高いrectを取り出して面積を計算する必要があります。
対象の高さがスタックのトップの高さと同じ場合
スタックのトップにあるrectの高さはスタックの中で最大なので、
スタックに入っている全てのrectの横幅が拡張されることになります。
なので、次のindexに進みます。
タイルの列の最後の位置まで到達した場合
スタックに積んである全てのrectの面積を計算し、最大の面積が更新されるかチェックします。
このプロセスを行の数繰り返せば最大面積が求められます。
このように、スタックを利用することで、タイル毎ごとに面積を計算する手間を省くことができます。
c++による最大長方形を求めるコード
今までの解説をもとに、コードを書きます。
#include <bits/stdc++.h>
using namespace std;
#define MAX 1400
struct Rectangle{
// indexの地点の高さ
int height;
// 始点のX
int pos;
};
// buf = Tの一行の配列
// size = Tの一行のサイズ
int getLargestRectangle(int size,int buf[]){
// stackとして長方形を保存
stack<Rectangle> s;
int maxV = 0;
// 配列の最後を0にすることで、範囲外後に最大面積を計算するようにする
buf[size] = 0;
// stoperまで回す
for(int i = 0;i <= size;++i){
Rectangle rect;
// 高さ代入
rect.height = buf[i];
// 横の位置は計算を始める時点の位置
rect.pos = i;
// stack空ならば追加
if(s.empty()){
s.push(rect);
}
else{
// stackのトップにあるrectの高さより高い場合
if(s.top().height < rect.height){
s.push(rect);
}
// stackのトップにあるrectの高さよりも低い場合(保存してあった最大の高さが無効になるので、無効になる高さの面積を計算する必要がある)
else if(s.top().height > rect.height){
// 新しく積むrectの幅を出すために保存しておく。
int targetX = i;
// スタックに入っているrectが対象のrectの高さ以上の場合最大面積を計算する
while(!s.empty() && s.top().height >= rect.height){
Rectangle pre = s.top();
s.pop();
// 面積を計算する
int area = pre.height * (i - pre.pos);
maxV = max(maxV,area);
// 始点Xを入れ替える(stackに積むrectの高さは取り出したrectの高さよりも低いので、取り出した地点が、長方形を計算する際のX座標になる)
targetX = pre.pos;
}
rect.pos = targetX;
s.push(rect);
}
}
}
return maxV;
}
int H,W;
// タイル情報を2次元で保存0:綺麗なタイル,1:汚れたタイル
int tiles[MAX][MAX];
// 高さを格納する2次元配列
int T[MAX][MAX];
int getLargestRectangle(){
// 各々の地点における高さを格納するプロセス
for(int j = 0;j < W;++j){
for(int i = 0;i < H;++i){
// 汚れたタイル
if(tiles[i][j]){
T[i][j] = 0;
}
else{
// 対象のindex地点の高さを格納する
// 上の地点 + 1の高さになる
T[i][j] = (i > 0) ? T[i - 1][j] + 1 : 1;
}
}
}
// 最大面積保存用
int maxV = 0;
// 最大高さ分回す
for(int i = 0;i < H;++i){
maxV = max(maxV,getLargestRectangle(W,T[i]));
}
return maxV;
}
int main(){
scanf("%d %d",&H,&W);
for(int i = 0;i < H;++i){
for(int j = 0;j < W;++j){
scanf("%d",&tiles[i][j]);
}
}
printf("%d\n",getLargestRectangle());
}最大長方形を求める問題の解法をまとめる
1.タイルの列における高さを保存する配列を作る。
2.高さを保存する配列を行ごとに回して、一行における最大の面積を求める。
その際にスタックを利用して、計算量を減らすようにする。
