C++で最大値が範囲[L, R]に収まる部分配列の個数を数える方法

問題の概要

正の整数からなる配列 A と、2つの正整数 L・R が与えられます。このとき、「部分配列内の最大要素の値が L 以上 R 以下」という条件を満たす、連続した空でない部分配列の個数を求めるのが目的です。

例えば、A = [2,1,4,3]、L = 2、R = 3 の場合を考えてみましょう。条件を満たす部分配列は [2]、[2,1]、[3] の3つであるため、出力は 3 になります。

解法のアプローチ

この問題は、配列を一度走査するだけで O(n) の時間計算量で解けます。考え方のポイントは次の通りです。

• ret:最終的な答え(条件を満たす部分配列の総数)
• dp:「現在注目している位置で終わる、条件を満たす部分配列の数」
• prev:「R を超える要素が最後に出現したインデックス」(ここより左側しか使えない)

具体的には、以下の手順で処理を進めます。

• ret := 0、dp := 0、prev := -1 で初期化します。
• i を 0 から A のサイズ − 1 まで繰り返します。
  • A[i] < L かつ i > 0 の場合:A[i] は小さすぎますが、直前までの有効な部分配列の末尾にそのまま連結できるため、ret := ret + dp とします。
  • A[i] > R の場合:この要素以降はどの部分配列にも使えないため、prev := i、dp := 0 として区切り位置を更新します。
  • L ≤ A[i] ≤ R の場合:A[i] で終わる新しい有効な部分配列が i − prev 個生まれるため、dp := i − prev、ret := ret + dp とします。
• ループ終了後、ret を返します。

C++での実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int ret = 0;
        int dp = 0;
        int prev = -1;
        for(int i = 0; i < A.size(); i++){
            if(A[i] < L && i > 0){
                ret += dp;
            }
            if(A[i] > R){
                prev = i;
                dp = 0;
            }
            else if(A[i] >= L && A[i] <= R){
                dp = i - prev;
                ret += dp;
            }
        }
        return ret;
    }
};
main(){
    vector<int> v = {2,1,4,3};
    Solution ob;
    cout << (ob.numSubarrayBoundedMax(v, 2, 3));
}

入力

[2,1,4,3]
2
3

出力

3

計算量の評価

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n) です。また、使用する変数は ret・dp・prev の3つだけであり、追加のデータ構造が不要なため、空間計算量は O(1) で済みます。大きな入力に対しても非常に効率的に動作する点が魅力です。