C++で部分配列が山型（マウンテン）かどうかを判定する方法

この記事では、整数配列 arr[] と範囲 [L, R] が与えられたとき、その範囲に含まれる部分配列が山型（マウンテン）の形になっているかどうかを判定する方法を解説します。

「山型」とは、要素が途中まで単調に増加し、頂上から先は単調に減少していく、文字どおり山のような形状を持つ部分配列のことです。

問題の確認

具体例を見てみましょう。

入力 : arr[] = {1, 4, 2, 5, 6, 7, 3, 0}, 範囲 = [2, 7]
出力 : Yes

説明：

範囲 [2, 7] の部分配列 = {2, 5, 6, 7, 3, 0}
値がまず増加し、その後減少しているため山型です。

解法アプローチ

この問題に対するシンプルな解決策は、補助配列を活用する方法です。あらかじめ前処理を行っておくことで、任意の範囲について高速に判定できるようになります。

具体的な手順は次のとおりです。

• left[i]：位置 i まで見たときに、増加が続く最後のインデックスを記録します。
• right[i]：位置 i 以降で、値の減少が始まる最初のインデックスを記録します。
• 範囲 [L, R] が山型であるかどうかは、「right[L] >= left[R]」という条件式ひとつで判定できます。

前処理には O(N)、範囲ごとの判定には O(1) しかかからないため、複数の範囲に対して繰り返し問い合わせる場合にも非常に効率的です。

C++での実装例

上記の解法を実装したプログラムがこちらです。

#include <iostream>
using namespace std;
int processArray(int arr[], int N, int left[], int right[]){
   left[0] = 0;
   int increasingValR = 0;
   for (int i = 1; i < N; i++){
      if (arr[i] > arr[i - 1])
         increasingValR = i;
      left[i] = increasingValR;
   }
   right[N - 1] = N - 1;
   int decreasingValL = N - 1;
   for (int i = N - 2; i >= 0; i--){
      if (arr[i] > arr[i + 1])
         decreasingValL = i;
      right[i] = decreasingValL;
   }
}
bool isMountainSubArray(int arr[], int left[], int right[], int L, int R){
   return (right[L] >= left[R]);
}
int main(){
   int arr[] = {2, 3, 2, 4, 4, 6, 3, 2};
   int N = sizeof(arr) / sizeof(int);
   int left[N], right[N];
   processArray(arr, N, left, right);
   int L = 0;
   int R = 2;
   if (isMountainSubArray(arr, left, right, L, R))
      cout<<"The subarray is in mountain form";
   else
      cout<<"The subarray is not in mountain form";
   return 0;
}

出力結果

The subarray is in mountain form

コードの解説

このプログラムでは、配列 {2, 3, 2, 4, 4, 6, 3, 2} の範囲 [0, 2]、つまり部分配列 {2, 3, 2} を対象に判定を行っています。「2 → 3」と増加した後「3 → 2」と減少しているため、これは山型であり、正しく判定できていることがわかります。

processArray() 関数が前処理として left 配列と right 配列を構築し、isMountainSubArray() 関数が条件式によって実際の判定を行います。判定自体は比較一回で完了するため、大量の範囲クエリを扱うケースでも高いパフォーマンスを発揮するアプローチです。