C++で解く！絶対差が制限以下となる最長の連続部分配列を求めるアルゴリズム

問題概要

整数型の配列 nums と整数 limit が与えられます。「部分配列内の任意の2要素の絶対差が limit 以下である」という条件を満たす、最も長い空でない連続部分配列（サブアレイ）の長さを求めてください。

例として、nums = [8,2,4,7]、limit = 4 が入力された場合の出力は 2 になります。すべての部分配列を確認してみましょう。

• [8] → |8−8| = 0 ≤ 4（条件を満たす）

• [8,2] → |8−2| = 6 > 4（条件を満たさない）

• [8,2,4] → |8−2| = 6 > 4（条件を満たさない）

• [8,2,4,7] → |8−2| = 6 > 4（条件を満たさない）

• [2] → |2−2| = 0 ≤ 4（条件を満たす）

• [2,4] → |2−4| = 2 ≤ 4（条件を満たす）

• [2,4,7] → |2−7| = 5 > 4（条件を満たさない）

• [4] → |4−4| = 0 ≤ 4（条件を満たす）

• [4,7] → |4−7| = 3 ≤ 4（条件を満たす）

• [7] → |7−7| = 0 ≤ 4（条件を満たす）

以上より、条件を満たす最長の部分配列は長さ 2 となります。

解法のアプローチ：スライディングウィンドウ × モノトニックデック

この問題は「スライディングウィンドウ」と「モノトニックデック（単調両端キュー）」を組み合わせると効率的に解けます。全ペアを毎回チェックすると非効率ですが、ウィンドウ内の最大値と最小値をそれぞれ O(1) で取得できれば、その差が limit 以下かどうかだけで判定できます。

アルゴリズムの手順

• ret := 0、i := 0、j := 0 で初期化します（i はウィンドウの右端、j は左端を表します）。

• 最大値管理用のデック maxD と、最小値管理用のデック minD を定義します。

• n := nums のサイズとします。

• i を 0 から n−1 まで動かしながら、以下を繰り返します。

  • maxD が空でなく、末尾の要素が nums[i] より小さい間、末尾の要素を削除します。

  • minD が空でなく、末尾の要素が nums[i] より大きい間、末尾の要素を削除します。

  • nums[i] を maxD と minD の末尾に追加します。

  • (maxD の先頭 − minD の先頭) > limit である間、次を繰り返します。

    • nums[j] が maxD の先頭と等しければ、maxD の先頭を削除します。

    • nums[j] が minD の先頭と等しければ、minD の先頭を削除します。

    • j を 1 増やし、ウィンドウの左端を縮めます。

  • ret := max(ret, i − j + 1) で答えを更新します。

• 最後に ret を返します。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestSubarray(vector<int>& nums, int limit) {
      int ret = 0;
      int j = 0;
      deque<int> maxD;
      deque<int> minD;
      int n = nums.size();
      for (int i = 0; i < n; i++) {
         while (!maxD.empty() && maxD.back() < nums[i])
            maxD.pop_back();
         while (!minD.empty() && minD.back() > nums[i])
            minD.pop_back();
         maxD.push_back(nums[i]);
         minD.push_back(nums[i]);
         while (maxD.front() - minD.front() > limit) {
            if (nums[j] == maxD.front())
               maxD.pop_front();
            if (nums[j] == minD.front())
               minD.pop_front();
            j++;
         }
         ret = max(ret, i - j + 1);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {8,2,4,7};
   cout << (ob.longestSubarray(v, 4));
}

入力

{8,2,4,7}, 4

出力

2

計算量の評価

時間計算量： O(n) ― 各要素は各デックに高々1回追加され、高々1回削除されるだけだからです。
空間計算量： O(n) ― 2つのデックがウィンドウ内の要素を保持するためです。