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

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

本文概述

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

高效方法：这个想法是使用在 的下一个更大的元素文章.步骤如下：

  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

时间复杂度：O(n)

辅助空间：O(n)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: