C++の制限以下の絶対差分を持つ最長の連続サブアレイ

numsと呼ばれる整数の配列と整数の制限があるとすると、このサブ配列の任意の2つの項目間の絶対差が指定された制限以下になるように、最も長い空でないサブ配列のサイズを見つける必要があります。

したがって、入力が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です。

これを解決するには、次の手順に従います-

• ret：=0、i：=0、j：=0

• 1つのdequemaxDと別のdequeminDを定義します

• n：=numsのサイズ

• 初期化i：=0の場合、i

  • （maxDが空ではなく、maxD

    • maxDから最後の要素を削除する

  • 一方（minDは空ではなく、minDの最後の要素> nums [i]）、do-

    • minDから最後の要素を削除する

  • maxDの最後にnums[i]を挿入します

  • minDの最後にnums[i]を挿入します

  • while（maxDの最初の要素-minDの最初の要素）> k、do-

    • nums [j]がmaxDの最初の要素と同じである場合、-

      • maxDからフロント要素を削除します

    • nums [j]がminDの最初の要素と同じである場合、-

      • minDからフロント要素を削除します

    • （jを1増やします）

  • ret：=retの最大値と（i --j + 1）

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestSubarray(vector<int>& nums, int k) {
      int ret = 0;
      int i = 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() > k) {
            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 = {7,8,2,4};
   cout << (ob.longestSubarray(v, 4));
}

入力

{7,8,2,4}, 4

出力

2