本文概述
- C ++
- Python3
例子:
输入:arr [] = {3, 2, 4, 5, 6, 1, 9} Y = 3简单的方法:简单的想法是遍历范围内的每个索引i[0, N – Y]使用另一个循环从i遍历th(i + Y – 1)的索引th索引, 然后计算大小子数组中的最小和最大元素?并因此计算出该最大和最小元素的差th迭代。最后, 通过检查差异, 评估最小差异。
输出: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。
时间复杂度:O(N * Y)
【所有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 + = 1submax.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 + = 1submin.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)
推荐阅读
- C和C++之间有什么区别(有哪些区别?)
- 算法设计(跳转搜索算法原理解析和实现)
- 设计和实现特殊的栈数据结构|添加了空间优化版本
- 允许向左/向右/向下和向上移动的最小成本路径
- 算法题(将一个数组拆分成两个相等的和子数组)
- pe装系统图文详细教程
- 本文告诉你bios升级有啥用
- 萝卜家园win10纯净版安装图文详细教程
- 一键系统之家系统安装win7的办法