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

本文概述

C ++
Python3

给定一个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)
【所有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

输出如下：