C++で配列の全ウィンドウサイズにおける「最小値の最大値」を求める方法

問題の概要

サイズnの整数配列arr[]が与えられたとき、ウィンドウサイズを1からnまで変化させながら、それぞれのサイズにおける「最小値の最大値」を求めるのが本問題です。

具体的には、各ウィンドウサイズkについて、配列内に存在するすべての長さkの連続部分配列(ウィンドウ)を調べ、その最小値を記録します。さらに、それらの最小値の中から最大のものを取り出して出力します。

入力例

arr[] = {4, 1, 2, 4, 5, 1, 2, 4}

出力例

5 4 2 1 1 1 1 1

計算過程の解説

ウィンドウサイズ :
1 => ウィンドウ { (4), (1), (2), (4), (5), (1), (2), (4) } => 各最小値 = {4, 1, 2, 4, 5, 1, 2, 4} => 最小値の最大値 = 5
2 => ウィンドウ { (4,1), (1,2), (2,4), (4,5), (5,1), (1,2), (2,4) } => 各最小値 = {1, 1, 2, 4, 1, 1, 2} => 最小値の最大値 = 4
3 => ウィンドウ { (4,1,2), (1,2,4), (2,4,5), (4,5,1), (5,1,2), (1,2,4) } => 各最小値 = {1, 1, 2, 1, 1, 1} => 最小値の最大値 = 2
4 => ウィンドウ { (4,1,2,4), (1,2,4,5), (2,4,5,1), (4,5,1,2), (5,1,2,4) } => 各最小値 = {1, 1, 1, 1, 1} => 最小値の最大値 = 1
5 => ウィンドウ { (4,1,2,4,5), (1,2,4,5,1), (2,4,5,1,2), (4,5,1,2,4) } => 各最小値 = {1, 1, 1, 1} => 最小値の最大値 = 1
6 => ウィンドウ { (4,1,2,4,5,1), (1,2,4,5,1,2), (2,4,5,1,2,4) } => 各最小値 = {1, 1, 1} => 最小値の最大値 = 1
7 => ウィンドウ { (4,1,2,4,5,1,2), (1,2,4,5,1,2,4) } => 各最小値 = {1, 1} => 最小値の最大値 = 1
8 => ウィンドウ { (4,1,2,4,5,1,2,4) } => 各最小値 = {1} => 最小値の最大値 = 1

解法1: 全ウィンドウを走査する素朴なアプローチ

最も直感的な方法は、サイズ1からnまでのすべてのウィンドウを実際に生成して調べることです。各ウィンドウサイズkごとに、開始位置iを0からn−kまで動かしながら長さkの部分配列を走査して最小値を求め、得られた最小値のうち最大のものを記録していきます。

この方法は実装が非常に簡単ですが、三重ループが必要となるため時間計算量はO(n³)となり、大きな入力には不向きです。

実装例(C++)

#include <iostream>
using namespace std;

// サイズkのウィンドウにおける最小値の最大値を求めて出力する
void printMaxMinWindowK(int arr[], int n, int k) {
    int maxMin = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int minEle = arr[i];
        for (int j = 1; j < k; j++) {
            if (arr[i + j] < minEle)
                minEle = arr[i + j];
        }
        if (minEle > maxMin)
            maxMin = minEle;
    }
    cout << maxMin << endl;
}

int main() {
    int arr[] = {4, 1, 2, 4, 5, 1, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int k = 1; k <= n; k++) {
        cout << "Window Size : " << k << ", maximum of minimum : ";
        printMaxMinWindowK(arr, n, k);
    }
    return 0;
}

出力

Window Size : 1, maximum of minimum : 5
Window Size : 2, maximum of minimum : 4
Window Size : 3, maximum of minimum : 2
Window Size : 4, maximum of minimum : 1
Window Size : 5, maximum of minimum : 1
Window Size : 6, maximum of minimum : 1
Window Size : 7, maximum of minimum : 1
Window Size : 8, maximum of minimum : 1

解法2: スタックを活用した効率的なアプローチ(O(n))

より効率的な解法では、補助配列とスタックを使用します。各要素arr[i]について、「左側で自分より小さい直近の要素の位置(prev)」と「右側で自分より小さい直近の要素の位置(next)」をスタックで求めます。

すると、arr[i]が最小値となるウィンドウの長さは「next[i] − prev[i] − 1」として計算できます。この情報をもとに各ウィンドウ長の答えをmaxOfMin配列に記録し、最後に長いウィンドウ側から短いウィンドウ側へ累積最大値を伝播させれば、すべてのウィンドウサイズの答えをO(n)で求められます。

実装例(C++)

#include <iostream>
#include <stack>
using namespace std;

void printMaxMinWindow(int arr[], int n) {
    stack<int> s;
    int prev[n], next[n];

    // 初期化: 境界外を表す値を設定
    for (int i = 0; i < n; i++) {
        prev[i] = -1;
        next[i] = n;
    }

    // 左側で自分より小さい直近の要素を求める
    for (int i = 0; i < n; i++) {
        while (!s.empty() && arr[s.top()] >= arr[i])
            s.pop();
        if (!s.empty())
            prev[i] = s.top();
        s.push(i);
    }

    // スタックを空にする
    while (!s.empty())
        s.pop();

    // 右側で自分より小さい直近の要素を求める
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && arr[s.top()] >= arr[i])
            s.pop();
        if (!s.empty())
            next[i] = s.top();
        s.push(i);
    }

    // arr[i]が最小値になるウィンドウ長lenの答えを更新
    int maxOfMin[n + 1];
    for (int i = 0; i <= n; i++)
        maxOfMin[i] = 0;

    for (int i = 0; i < n; i++) {
        int len = next[i] - prev[i] - 1;
        maxOfMin[len] = max(maxOfMin[len], arr[i]);
    }

    // 長いウィンドウの結果を短いウィンドウへ伝播させる
    for (int i = n - 1; i >= 1; i--)
        maxOfMin[i] = max(maxOfMin[i], maxOfMin[i + 1]);

    for (int i = 1; i <= n; i++)
        cout << "Window Size: " << i << ", maximum of minimum : " << maxOfMin[i] << endl;
}

int main() {
    int arr[] = {4, 1, 2, 4, 5, 1, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printMaxMinWindow(arr, n);
    return 0;
}

出力

Window Size: 1, maximum of minimum : 5
Window Size: 2, maximum of minimum : 4
Window Size: 3, maximum of minimum : 2
Window Size: 4, maximum of minimum : 1
Window Size: 5, maximum of minimum : 1
Window Size: 6, maximum of minimum : 1
Window Size: 7, maximum of minimum : 1
Window Size: 8, maximum of minimum : 1

まとめ

素朴な解法はO(n³)、スタックを用いた解法はO(n)の時間計算量で動作します。大規模な配列を扱う場合は、「次に小さい要素」をスタックで効率よく求めるアプローチを採用することで、大幅な高速化が可能になります。