2次元配列のピーク要素を効率的に求めるアルゴリズム【C++実装例つき】

ピーク要素とは

ある要素が、その上下左右の4つの隣接要素すべてと比べて「それら以上の値」を持つとき、その要素をピーク要素と呼びます。隣接要素とは、対象の要素の上・下・左・右に位置する要素のことであり、斜め方向の要素は隣接要素として考慮しません。また、行列の端にある要素については、境界の外側を無限大として扱うものとします。

なお、1つの行列の中にピーク要素が複数存在することもあります。さらに重要な点として、ピーク要素は必ずしも行列内で最大の要素であるとは限りません。

入力と出力

入力:
10  8  10  10
14 13  12  11
15  9  11  11
15  9  11  21
16 17  19  20

出力:
21

この例では、行列のピーク要素は 21 です。

アルゴリズムの考え方

この問題は、すべての要素を順に調べる代わりに、中央の列に注目する二分探索的なアプローチで効率的に解くことができます。手順は以下の通りです。

1. 注目している列の中で最大の要素を見つける。
2. その要素が左右の隣接要素以上であれば、それがピーク要素。
3. 左隣の要素の方が大きければ、左半分の領域に対して再帰的に同じ処理を行う。
4. 右隣の要素の方が大きければ、右半分の領域に対して再帰的に同じ処理を行う。

findMaxMid(rows, mid, max)

入力: 行列の行数、注目する列番号、最大値を格納する出力用引数。

出力: 列内の最大値と、その行インデックスを更新して返します。

Begin
    maxIndex := 0
    for all rows r in the matrix, do
       if max < matrix[i, mid], then
          max = matrix[i, mid]
          maxIndex := r
    done
    return maxIndex
End

findPeakElement(rows, columns, mid)

入力: 行列の行数・列数、および注目する列の位置。

出力: 行列のピーク要素。

Begin
    maxMid := 0
    maxMidIndex := findMaxMid(rows, mid, maxMid)

    if mid is first or last column, then
       return maxMid

    if maxMid >= item of previous and next row for mid column, then
       return maxMid

    if maxMid is less than its left element, then
       res := findPeakElement(rows, columns, mid − mid/2)
       return res

    if maxMid is less than its right element, then
       res := findPeakElement(rows, columns, mid + mid/2)
       return res
End

C++による実装例

#include<iostream>
#define M 4
#define N 4
using namespace std;

int arr[M][N] = {
    {10, 8, 10, 10},
    {14, 13, 12, 11},
    {15, 9, 11, 21},
    {16, 17, 19, 20}
};

int findMaxMid(int rows, int mid, int& max) {
    int maxIndex = 0;

    for (int i = 0; i < rows; i++) {   // 中央の列で最大の要素を探す
       if (max < arr[i][mid]) {
          max = arr[i][mid];
          maxIndex = i;
       }
    }
    return maxIndex;
}

int findPeakElement(int rows, int columns, int mid) {
    int maxMid = 0;
    int maxMidIndex = findMaxMid(rows, mid, maxMid);

    if (mid == 0 || mid == columns-1)  // 最初と最後の列では maxMid が最大
       return maxMid;
    // maxMid 自体がピークである場合
    if (maxMid >= arr[maxMidIndex][mid-1] && maxMid >= arr[maxMidIndex][mid+1])
       return maxMid;

    if (maxMid < arr[maxMidIndex][mid-1])  // 左隣の要素の方が大きい場合
       return findPeakElement(rows, columns, mid - mid/2);
    return findPeakElement(rows, columns, mid+mid/2);
}

int main() {
    int row = 4, col = 4;
    cout << "The peak element is: " << findPeakElement(row, col, col/2);
}

出力結果

The peak element is: 21

計算量について

このアルゴリズムでは、処理を進めるごとに探索対象の列の範囲が約半分に縮小していきます。そのため、時間計算量は O(n log m)（n は行数、m は列数）となります。全要素を単純に走査する O(n×m) の素朴な手法と比べ、大きな行列を扱う際に大幅な高速化が期待できます。