# 所有Y大小子数组中最大和最小元素之间的最小差异

2021年4月15日17:19:43 发表评论 946 次浏览

## 本文概述

{2, 4, 5}, 其中最大元素= 5而最小元素= 2差= 3 {4, 5, 6}其中最大元素= 6而最小元素= 4差= 2
{5, 6, 1}, 其中最大元素= 6, 最小元素= 1差= 5
{6, 1, 9}其中最大元素= 9而最小元素= 6差= 3这些最小值中有2。

{3, 3, 2, 2}最大元素= 3, 最小元素= 2差= 1这些最小值中的1。

1. 建立两个数组maxarr []和尖塔[], 在哪里maxarr []将存储元素的索引, 该索引比该元素的下一个大一世th编号和尖塔[]将存储下一个元素的索引, 该索引小于一世th编号.
2. 用初始化一个堆栈0在以上两种情况下都存储索引。
3. 对于每个索引, 一世范围中[0, N – Y], 使用嵌套循环和滑动窗口方法形成两个数组亚最大和次分这些数组将在子数组中存储最大和最小元素一世th迭代。
4. 最后, 计算最小差异​​。

## C ++

``````//C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

//Function to get the maximum of all
//the subarrays of size Y
vector<int> get_submaxarr( int * arr, int n, int y)
{
int j = 0;
stack<int> stk;

//ith index of maxarr array
//will be the index upto which
//Arr[i] is maximum
vector<int> maxarr(n);
stk.push(0);

for ( int i = 1; i <n; i++) {

//Stack is used to find the
//next larger element and
//keeps track of index of
//current iteration
while (stk.empty() == false
and arr[i]> arr[stk.top()]) {

maxarr[stk.top()] = i - 1;
stk.pop();
}
stk.push(i);
}

//Loop for remaining indexes
while (!stk.empty()) {

maxarr[stk.top()] = n - 1;
stk.pop();
}
vector<int> submax;

for ( int i = 0; i <= n - y; i++) {

//j <i used to keep track
//whether jth element is
//inside or outside the window
while (maxarr[j] <i + y - 1
or j <i) {
j++;
}

submax.push_back(arr[j]);
}

//Return submax
return submax;
}

//Function to get the minimum for
//all subarrays of size Y
vector<int> get_subminarr( int * arr, int n, int y)
{
int j = 0;

stack<int> stk;

//ith index of minarr array
//will be the index upto which
//Arr[i] is minimum
vector<int> minarr(n);
stk.push(0);

for ( int i = 1; i <n; i++) {

//Stack is used to find the
//next smaller element and
//keeping track of index of
//current iteration
while (stk.empty() == false
and arr[i] <arr[stk.top()]) {

minarr[stk.top()] = i;
stk.pop();
}
stk.push(i);
}

//Loop for remaining indexes
while (!stk.empty()) {

minarr[stk.top()] = n;
stk.pop();
}

vector<int> submin;

for ( int i = 0; i <= n - y; i++) {

//j <i used to keep track
//whether jth element is inside
//or outside the window

while (minarr[j] <= i + y - 1
or j <i) {
j++;
}

submin.push_back(arr[j]);
}

//Return submin
return submin;
}

//Function to get minimum difference
void getMinDifference( int Arr[], int N, int Y)
{
//Create submin and submax arrays
vector<int> submin
= get_subminarr(Arr, N, Y);

vector<int> submax
= get_submaxarr(Arr, N, Y);

//Store initial difference
int minn = submax[0] - submin[0];
int b = submax.size();

for ( int i = 1; i <b; i++) {

//Calculate temporary difference
int dif = submax[i] - submin[i];
minn = min(minn, dif);
}

//Final minimum difference
cout <<minn <<"\n" ;
}

//Driver Code
int main()
{
//Given array arr[]
int arr[] = { 1, 2, 3, 3, 2, 2 };
int N = sizeof arr /sizeof arr[0];

//Given subarray size
int Y = 4;

//Function Call
getMinDifference(arr, N, Y);
return 0;
}``````

## Python3

``````# Python3 program for the above approach

# Function to get the maximum of all
# the subarrays of size Y
def get_submaxarr(arr, n, y):

j = 0
stk = []

# ith index of maxarr array
# will be the index upto which
# Arr[i] is maximum
maxarr = [ 0 ] * n
stk.append( 0 )

for i in range ( 1 , n):

# Stack is used to find the
# next larger element and
# keeps track of index of
# current iteration
while ( len (stk)> 0 and
arr[i]> arr[stk[ - 1 ]]):
maxarr[stk[ - 1 ]] = i - 1
stk.pop()

stk.append(i)

# Loop for remaining indexes
while (stk):
maxarr[stk[ - 1 ]] = n - 1
stk.pop()

submax = []

for i in range (n - y + 1 ):

# j <i used to keep track
# whether jth element is
# inside or outside the window
while (maxarr[j] <i + y - 1 or
j <i):
j + = 1

submax.append(arr[j])

# Return submax
return submax

# Function to get the minimum for
# all subarrays of size Y
def get_subminarr(arr, n, y):

j = 0
stk = []

# ith index of minarr array
# will be the index upto which
# Arr[i] is minimum
minarr = [ 0 ] * n
stk.append( 0 )

for i in range ( 1 , n):

# Stack is used to find the
# next smaller element and
# keeping track of index of
# current iteration
while (stk and arr[i] <arr[stk[ - 1 ]]):
minarr[stk[ - 1 ]] = i
stk.pop()

stk.append(i)

# Loop for remaining indexes
while (stk):
minarr[stk[ - 1 ]] = n
stk.pop()

submin = []

for i in range (n - y + 1 ):

# j <i used to keep track
# whether jth element is inside
# or outside the window
while (minarr[j] <= i + y - 1 or
j <i):
j + = 1

submin.append(arr[j])

# Return submin
return submin

# Function to get minimum difference
def getMinDifference(Arr, N, Y):

# Create submin and submax arrays
submin = get_subminarr(Arr, N, Y)
submax = get_submaxarr(Arr, N, Y)

# Store initial difference
minn = submax[ 0 ] - submin[ 0 ]
b = len (submax)

for i in range ( 1 , b):

# Calculate temporary difference
diff = submax[i] - submin[i]
minn = min (minn, diff)

# Final minimum difference
print (minn)

# Driver code

# Given array arr[]
arr = [ 1 , 2 , 3 , 3 , 2 , 2 ]
N = len (arr)

# Given subarray size
Y = 4

# Function call
getMinDifference(arr, N, Y)

# This code is contributed by Stuti Pathak``````

``1``