C++の特定の配列のすべてのウィンドウサイズの最小値の最大値を見つけます

この問題では、サイズnの配列arr[]が与えられます。私たちのタスクは、特定の配列のすべてのウィンドウサイズの最小値の最大値を見つけることです。

問題の説明 −1からnまで変化するウィンドウサイズの最小値の最大値を見つける必要があります。このために、指定されたウィンドウサイズのサブアレイを検討し、各サブアレイの最小要素を見つけてから、すべての最小値の最大値を見つけます。

問題を理解するために例を見てみましょう

入力

arr[] = {4, 1, 2, 4, 5, 1, 2, 4}

出力

5 4 2 1 1 1 1 1

説明

Window Size :
1 => windows { (4), (1), (2), (4), (5), (1), (2), (4) } => minimum = {4, 1, 2, 4, 5, 1, 2, 4} => maximum of minimums = 5
2 => windows { (4, 1), (1, 2), (2, 4), (4, 5), (5, 1), (1, 2), (2, 4) } => minimum = {1, 1, 2, 4, 1, 1, 2} => maximum of minimums = 4
3 => windows { (4, 1, 2), (1, 2, 4), (2, 4, 5), (4, 5, 1), (5, 1, 2), (1, 2, 4) } => minimum = {1, 1, 2, 1, 1, 1} => maximum of minimums = 2
4 => windows { (4, 1, 2, 4), (1, 2, 4, 5), (2, 4, 5, 1), (4, 5, 1, 2), (5, 1, 2, 4) }=> minimum = {1, 1, 1, 1, 1} => maximum of minimums = 1
5 => windows { (4, 1, 2, 4, 5), (1, 2, 4, 5, 1), (2, 4, 5, 1, 2), (4, 5, 1, 2, 4) } => minimum = {1, 1, 1, 1} => maximum of minimums = 1
6 => windows { (4, 1, 2, 4, 5, 1), (1, 2, 4, 5, 1, 2), (2, 4, 5, 1, 2, 4) } => minimum = {1, 1, 1} => maximum of minimums = 1
7 => windows { (4, 1, 2, 4, 5, 1, 2), (1, 2, 4, 5, 1, 2, 4) } => minimum = {1, 1} => maximum of minimums = 1
7 => windows { (4, 1, 2, 4, 5, 1, 2, 4) } => minimum = {1} => maximum of
minimums = 1

ソリューションアプローチ

この問題の簡単な解決策は、サイズ1からnのすべてのウィンドウを作成することです。次に、指定されたサイズのウィンドウごとに、指定されたサイズのすべてのサブ配列を検索します。配列については、各サブ配列の最小値を見つけて、すべての最小値の最大値を返します。

各ウィンドウサイズの反復の最後に、最小値のすべての最大値をscalaで出力します

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
void printMaxMinWindowK(int arr[], int n, int k) {
   int maxMin = -1;
   int minEle = -1;
   for (int i = 0; i <= n-k; i++) {
      minEle = arr[i];
      for (int j = 1; j < k; j++) {
         if (arr[i+j] < minEle)
            minEle = arr[i+j];
      }
      if (minEle > maxMin)
         maxMin = minEle;
   }
   cout<<maxMin<<endl;
}
int main() {
   int arr[] = {4, 1, 2, 4, 5, 1, 2, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   for(int i = 1; i < n; i++){
      cout<<"Window Size :"<<i<<", maximum of minimum : ";
      printMaxMinWindowK(arr, n, i);
   }
   return 0;
}

出力

Window Size :1, maximum of minimum : 70
Window Size :2, maximum of minimum : 30
Window Size :3, maximum of minimum : 20
Window Size :4, maximum of minimum : 10
Window Size :5, maximum of minimum : 10
Window Size :6, maximum of minimum : 10

代替ソリューション

この問題の簡単な解決策は、追加のメモリスペースを使用して、補助アレイを作成することです。配列を使用して、現在の要素の次に小さい要素を格納します。そしてもう1つは、前の最小要素を格納します。これらの配列を使用して、インデックスiの配列要素の要素を見つけます。要素arr[i]は、長さが「right [i] --left[i]+1」のウィンドウの最小値です。これを使用して、指定されたウィンドウの最小値の最大値を見つけます。

ソリューションの動作を説明するプログラム

例

#include <iostream>
#include<stack>
using namespace std;
void printMaxMinWindow(int arr[], int n) {
   stack<int> s;
   int prev[n+1];
   int next[n+1];
   for (int i=0; i<n; i++) {
      prev[i] = -1;
      next[i] = n;
   }
   for (int i=0; i<n; i++) {
      while (!s.empty() && arr[s.top()] >= arr[i])
         s.pop();
         if (!s.empty())
            prev[i] = s.top();
            s.push(i);
   }
   while (!s.empty())
      s.pop();
      for (int i = n-1 ; i>=0 ; i-- ) {
         while (!s.empty() && arr[s.top()] >= arr[i])
            s.pop();
            if(!s.empty())
               next[i] = s.top();
               s.push(i);
      }
      int maxOfMin[n+1];
      for (int i=0; i<=n; i++)
         maxOfMin[i] = 0;
         for (int i=0; i<n; i++) {
            int len = next[i] - prev[i] - 1;
            maxOfMin[len] = max(maxOfMin[len], arr[i]);
         }
         for (int i=n-1; i>=1; i--)
            maxOfMin[i] = max(maxOfMin[i], maxOfMin[i+1]);
         for (int i=1; i<=n; i++)
            cout<<"Window Size: "<<i<<", maximum of minimum : "<<maxOfMin[i]<<endl;
}
int main() {
   int arr[] = {4, 1, 2, 4, 5, 1, 2, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   printMaxMinWindow(arr, n);
   return 0;
}

出力

Window Size: 1, maximum of minimum : 5
Window Size: 2, maximum of minimum : 4
Window Size: 3, maximum of minimum : 2
Window Size: 4, maximum of minimum : 1
Window Size: 5, maximum of minimum : 1
Window Size: 6, maximum of minimum : 1
Window Size: 7, maximum of minimum : 1
Window Size: 8, maximum of minimum : 1