C++で最も近い左と右の小さい要素間の最大の違いを見つける

コンセプト

与えられた整数の配列に関して、私たちのタスクは、配列内のすべての要素の最も近い左と右の小さい要素の間の最大絶対差を決定することです。右側または左側に小さい要素がない場合は注意する必要があります。任意の要素の側では、小さい要素としてゼロを受け入れます。ここで、たとえば左端の要素の場合、左側の最も近い小さい要素は0に設定されます。同様に、右端の要素の場合、右側の小さい要素は0に設定されます。

入力

arr[] = {3, 2, 9}

出力

2

小さいLS[]{0、0、2}

右小さいRS[]{2、0、0}

absの最大差分（LS [i]-RS [i]）=2-0 =2

入力

arr[] = {3, 5, 9, 8, 8, 10, 4}

出力

4

左小さいLS[]={0、3、5、5、5、8、3}

右小さいRS[]={0、4、8、4、4、4、0}

absの最大差分（LS [i]-RS [i]）=8-4 =4

メソッド

単純なソリューションを適用します。タスクは、最も近い左右の小さい要素を永久に見つけることであり、その後、左右の小さい要素間の最大差を更新します。これには、O（n ^ 2）時間がかかります。

ここでも、O（n）時間を消費する効率的なソリューションを実装します。ここでは、スタックを実装します。ここで興味深いのは、同じ関数を使用して左と右の両方を小さく計算することです。

入力配列を「Array[]」、配列のサイズを「n」と仮定します

左側の小さい要素をすべて決定します

• 新しい空のスタックSとアレイLSを構築します[]
• ここで、入力Array[]のすべての要素'Array [i]'について、'i'は0からn-1になります。
  • Sが空ではなく、Sの最上位要素が'Array [i]'：popS以上である場合
  • Sが空の場合：「Array[i]」には先行する小さい値がありませんLS[i] =0
  • else：'Array[i]'に最も近い小さい値はtopofstackLS [i] =S.top（）
  • 'Array[i]'をSにプッシュ
  • 右側の小さい要素をすべて決定します
• 最初は逆配列Array[]。配列を逆にすると、右が小さくなり、左が小さくなります。
• アレイRRS[]を作成し、手順1と2を繰り返して、RRS（LSの代わりに）を埋めます。
• 結果を-1として初期化し、elementArray[i]ごとに次のようにします。逆配列に関しては、Array[i]の右が小さい方がRRS[n-i-1]に格納されますreturnresult =max（result、LS [i] -RRS [n-i-1]）

例

// C++ program to find the difference b/w left and
// right smaller element of every element in array
#include<bits/stdc++.h>
using namespace std;
// Shows function to fill left smaller element for every
// element of Array[0..n1-1]. These values are filled
// in SE1[0..n1-1]
void leftSmaller(int Array[], int n1, int SE1[]){
   // Build an empty stack
   stack<int>S1;
   // Visit all array elements
   // Calculate nearest smaller elements of every element
   for (int i=0; i<n1; i++){
      // Used to keep removing top element from S1 while the top
      // element is greater than or equal to Array[i]
      while (!S1.empty() && S1.top() >= Array[i])
      S1.pop();
      // Used to store the smaller element of current element
      if (!S1.empty())
         SE1[i] = S1.top();
      // It has been seen that if all elements in S were greater than Array[i]
      else
         SE1[i] = 0;
         // Used to push this element
         S1.push(Array[i]);
      }
   }
   // Shows function returns maximum difference b/w Left &
   // right smaller element
   int findMaxDiff(int Array[], int n1){
      int LS1[n1]; // To store left smaller elements
      // find left smaller element of every element
      leftSmaller(Array, n1, LS1);
      // Determine right smaller element of every element
      // first reverse the array and do the same process
      int RRS1[n1]; // Used to store right smaller elements in
      // reverse array
      reverse(Array, Array + n1);
      leftSmaller(Array, n1, RRS1);
      // Determine maximum absolute difference b/w LS1 & RRS1
      // In the reversed array right smaller for Array[i] is
      // stored at RRS1[n1-i-1]
   int result1 = -1;
   for (int i=0 ; i< n1 ; i++)
   result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
   // return maximum difference between LS1 & RRS1
   return result1;
}
// Driver program
int main(){
   int Array[] = {3, 5, 9, 8, 8, 10, 4};
   int n = sizeof(Array)/sizeof(Array[0]);
   cout << "Maximum diff : "
   << findMaxDiff(Array, n) << endl;
   return 0;
}

出力

Maximum diff : 4