在C ++中找到给定数组中每个窗口大小的最小值的最大值
在这个问题中，我们得到了大小为n的数组arr []。我们的任务是找到给定数组中每个窗口大小的最小值的最大值。
问题描述-我们需要找到一个从1到n的最小窗口大小的最大值。为此，我们将考虑给定窗口大小的子数组，找到每个子数组的最小元素，然后找到所有最小值的最大值。
让我们举个例子来了解这个问题，
输入
arr[] = {4, 1, 2, 4, 5, 1, 2, 4}输出结果5 4 2 1 1 1 1 1
解释
视窗大小：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<<"视窗大小："<<i<<", maximum of minimum : ";
printMaxMinWindowK(arr, n, i);
}
return 0;
}
视窗大小：1, maximum of minimum : 70视窗大小：2, maximum of minimum : 30
视窗大小：3, maximum of minimum : 20
视窗大小：4, maximum of minimum : 10
视窗大小：5, maximum of minimum : 10
视窗大小：6, maximum of minimum : 10
替代解决方案
解决该问题的简单方法是使用额外的内存空间，创建一个辅助数组。我们将使用数组存储当前元素的下一个最小元素。另一个用于存储先前的最小元素。使用这些数组，我们将找到索引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<<"视窗大小： "<<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;
}
视窗大小： 1, maximum of minimum : 5视窗大小： 2, maximum of minimum : 4
视窗大小： 3, maximum of minimum : 2
视窗大小： 4, maximum of minimum : 1
视窗大小： 5, maximum of minimum : 1
视窗大小： 6, maximum of minimum : 1
视窗大小： 7, maximum of minimum : 1
视窗大小： 8, maximum of minimum : 1
以上是 在C ++中找到给定数组中每个窗口大小的最小值的最大值 的全部内容， 来源链接： utcz.com/z/348385.html
