ヒストグラム中の最大の長方形の面積

データの離散型分布を表すヒストグラム（柱状グラフ）は、長方形を共通の基線上に並べた多角形として描画されます。これらの長方形は同じ幅を持ちますが、異なる高さのものを含みます。ヒストグラムを表す多角形に含まれる最大の長方形の面積を求めて下さい。入力は各データに対応する長方形の高さの列に対応した n 個の要素からなる１次元配列とします。(source: ACM/ICPC University of Ulm Local Contest)

以下のように、２重ループによって長方形の範囲を選び、そこにできる最大の長方形の面積を計算して更新していけば、全体での最大の面積を求めることができます。これはO(n²)のアルゴリズムです。

001 int getRectangleAreaBF( int size, int buffer[] ){
002     int maxv = 0;
003     for ( int i = 0; i < size; i++ ){
004         for ( int j = i; j < size; j++ ){
005             int minh = INT_MAX;
006             for ( int k = i; k <= j; k++ ){
007                 minh = min( minh, buffer[k] );
008             }
009             maxv = max( maxv, minh*(j-i+1));
010         }
011     }
012     return maxv;
013 }

この問題は動的計画法を用いればO(n)のアルゴリズムで解くことができます。この解法は後で考える長方形探索などに応用することができるので重要です。

このアルゴリズムは部分問題の"未解決の"解をスタックに記憶していく、やや巧妙なテクニックを用います。スタックには、長方形の情報を記録します。各長方形は長方形の高さ height とその左端の位置 pos の情報を持たせます。まずスタックを空にし、ヒストグラムの各長方形 rect を左から右へ（i が 0 から n-1 まで）向かって順番に以下の処理を行います。

1. スタックが空の場合：
   　　スタックに rect を追加する


2. スタックの頂点にある長方形の高さが rect の高さより低い場合：
   　　スタックに rect を追加する


3. スタックの頂点にある長方形の高さが rect の高さと等しい場合：　
   　　何もしない


4. スタックの頂点にある長方形の高さが rect の高さより高い場合：
   
   
   
   • スタックが空でなく、スタックの頂点にある長方形の高さが rect の高さ以上である限り、スタックから長方形を取り出し、その面積を計算し最大値を更新する。長方形の横の長さは現在の位置 i と記録されている左端の位置 pos から計算できる。
   • スタックに rect を追加する。ただし、rect の左端の位置 pos は最後にスタックから取り出した長方形の pos の値とする
   
   
   
   
   

以下にアルゴリズムの流れを示します。位置 i におけるスタックには (i - 1) を右端としてできる未完成の長方形のリストが記録されます。図の 1 に示すように最初の５ステップでスタックには４つの未完成の長方形のリストが記録されます。




図の 2 で６番目のデータである高さ 2 の長方形を追加します。ここから図の 3,4,5 で、2 よりも高い長方形をスタックから順番に取り出し面積を計算します。最後に取り出された高さ 3 の長方形の位置は 1 なので、この現在追加しようとしている高さ 2 の長方形の位置を 1 とします。この時点でスタックには高さ 1 と 2 の未完成の長方形が記録されています。

以下はＰＯＪの解答プログラムです。

001 // pku 2559 (Largest Rectangle in a Histogram)
002 // O(n) algorithm
003 #include<stdio.h>
004 #include<iostream>
005 #include<stack>
006 #include<algorithm>
007 #define MAX 110000
008 typedef long long llong;
009 
010 using namespace std;
011 
012 struct Rectangle{ llong height;  int pos; };
013 
014 llong getRectangleArea( int size, llong buffer[]){
015     stack<Rectangle> S;
016     llong maxv = 0;
017     buffer[size] = 0;
018     
019     for ( int i = 0; i <= size; i++ ){
020         Rectangle rect;
021         rect.height = buffer[i];
022         rect.pos = i;
023         if ( S.empty() ){
024             S.push( rect );
025         } else {
026             if ( S.top().height < rect.height ){
027                 S.push( rect );
028             } else if ( S.top().height > rect.height ) {
029                 int target = i;
030                 while ( !S.empty() && S.top().height >= rect.height){
031                     Rectangle pre = S.top(); S.pop();
032                     llong area = pre.height * (i - pre.pos);
033                     maxv = max( maxv, area);
034                     target = pre.pos;
035                 }
036                 rect.pos = target;
037                 S.push(rect);
038             }
039         }
040     }
041     
042     return maxv;
043 }
044 
045 main(){
046     int size;
047     llong buffer[MAX+1];
048     
049     while(1){
050         scanf("%d", &size);
051         if ( size == 0 ) break;
052         for ( int i = 0; i < size; i++ ) scanf("%lld", &buffer[i]);
053         cout << getRectangleArea( size, buffer ) << endl;
054     }
055 }