本文概述
给定一个Array arr []大小ñ和整数Y, 任务是在所有大小子数组中的最大和最小元素之间找到所有差异中的最小值Y.
例子:
输入:arr [] = {3, 2, 4, 5, 6, 1, 9} Y = 3
输出:2
说明:
所有长度= 3的子数组为:{3, 2, 4}
其中最大元素= 4和最小元素= 2差= 2
{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。
输入:arr [] = {1, 2, 3, 3, 2, 2} Y = 4
输出:1
说明:所有长度= 4的子阵列为:{1, 2, 3, 3}最大元素= 3, 最小元素= 1差= 2 {2, 3, 3, 2}最大元素= 3, 最小元素= 2差= 1
{3, 3, 2, 2}最大元素= 3, 最小元素= 2差= 1这些最小值中的1。
简单的方法:简单的想法是遍历范围内的每个索引i[0, N – Y]使用另一个循环从i遍历th(i + Y – 1)的索引th索引, 然后计算大小子数组中的最小和最大元素ÿ并因此计算出该最大和最小元素的差th迭代。最后, 通过检查差异, 评估最小差异。
时间复杂度:O(N * Y)
辅助空间:O(1)
高效方法:这个想法是使用在 的下一个更大的元素文章.步骤如下:
- 建立两个数组maxarr []和尖塔[], 在哪里maxarr []将存储元素的索引, 该索引比该元素的下一个大一世th编号和尖塔[]将存储下一个元素的索引, 该索引小于一世th编号.
- 用初始化一个堆栈0在以上两种情况下都存储索引。
- 对于每个索引, 一世范围中[0, N – Y], 使用嵌套循环和滑动窗口方法形成两个数组亚最大和次分这些数组将在子数组中存储最大和最小元素一世th迭代。
- 最后, 计算最小差异。
下面是上述方法的实现:
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
时间复杂度:O(n)
辅助空间:O(n)