C++で2次元バイナリ行列から最大の長方形を求める方法(スタック活用)

問題概要

0と1から構成される2次元のバイナリ行列が与えられます。この行列の中から「1」だけで構成される最大の長方形を見つけ、その面積を返すのが本記事のテーマです。

この問題を解くには、以下の手順に従います。

getAns関数(ヒストグラム内の最大長方形を求める)

• 配列aを受け取る関数getAnsを定義します。
• スタックstを作成し、i := 0、ans := 0 と初期化します。
• iがaのサイズ未満である間、以下を繰り返します。
  • スタックが空、または a[i] がスタックトップの値以上の場合:iをstに挿入し、iを1増やします。
  • それ以外の場合:
    • height := a[スタックトップ] とし、スタックから削除(pop)します。
    • width := スタックが空なら i、それ以外は i − スタックトップ − 1 とします。
    • area := height × width とします。
    • ans := max(ans, area) と更新します。
• スタックが空になるまで、同じ要領で処理を続けます。
  • height := a[スタックトップ] とし、スタックから削除します。
  • width := stが空ならaのサイズ、それ以外は aのサイズ − スタックトップ − 1 とします。
  • area := height × width とします。
  • ans := max(ans, area) と更新します。
• ansを返します。

mainメソッドでの処理

• ans := 0、n := xの行数 とします。
• nが0なら0を返します。
• m := x[0]の列数 とします。
• サイズmの配列heightを作成します。
• iを0からn−1まで繰り返します。
  • jを0からm−1まで繰り返します。
    • x[i][j] が '1' なら height[j] を1増やし、そうでなければ height[j] := 0 とします。
  • ans := max(ans, getAns(height)) と更新します。
• ansを返します。

アルゴリズムのポイント

各行を走査するたびに、その時点での各列の「連続する1の高さ」をheight配列に記録しています。これは、ある行までを見たときのヒストグラムとみなすことができます。ヒストグラム内で作れる最大の長方形は、単調増加スタックを用いることで効率的に求められます。

スタックにはインデックスを格納し、対応する高さが常に昇順になるよう管理します。現在の高さがスタックトップより小さい場合、それより高い柱ではこれ以上長方形を伸ばせないため、その時点で面積を確定させてpopします。幅は「現在位置i」と「pop後のスタックトップ」の間隔から算出されます。

計算量

時間計算量は O(n × m)、空間計算量は O(m) となります(nは行数、mは列数)。すべての長方形候補を総当たりする方法(O(n²m²))と比べ、大幅に高速なのが特徴です。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int getAns(vector<int> a){
        stack<int> st;
        int i = 0;
        int ans = 0;
        while(i < a.size()){
            if(st.empty() || a[i] >= a[st.top()]){
                st.push(i);
                i++;
            } else {
                int height = a[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                int area = height * width;
                ans = max(ans, area);
            }
        }
        while(!st.empty()){
            int height = a[st.top()];
            st.pop();
            int width = st.empty() ? a.size() : a.size() - st.top() - 1;
            int area = height * width;
            ans = max(ans, area);
        }
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& x) {
        int ans = 0;
        int n = x.size();
        if(!n) return 0;
        int m = x[0].size();
        vector<int> height(m);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(x[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            ans = max(ans, getAns(height));
        }
        return ans;
    }
};

int main(){
    vector<vector<char>> v = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    Solution ob;
    cout << ob.maximalRectangle(v);
    return 0;
}

入力

{{'1','0','1','0','0'},
{'1','0','1','1','1'},
{'1','1','1','1','1'},
{'1','0','0','1','0'}
}

出力

6

この入力では、2行目と3行目の2〜4列目にわたる 2 × 3 = 6 マスの長方形が最大となるため、出力は 6 になります。