查找给定数组中每个窗口大小的最小值的最大值


难度级别 中等
经常问 亚马逊 指令 Flipkart SAP实验室 百会
排列 滑动窗口

给定大小为n的数组a []。 对于从1到n in的每个窗口大小 排列 打印或找到给定数组中每个窗口大小的最小值的最大值。

查找给定数组中每个窗口大小的最小值的最大值

使用案列

输入: a [] = {10,20,30,50,10,70,30}

输出: 70 30 20 10 10 10 10

输入: a [] = {10,20,30}

输出: 30

用于查找每个窗口大小的最小值最大值的朴素方法

算法

  1. 初始化大小为n的数组a []。
  2. 遍历数组a []。 初始化一个整数变量以存储最大值的最小值,并将其值设置为INT_MIN。
  3. 之后,遍历数组大小等于外部循环当前索引的所有窗口。 初始化变量以存储当前窗口的最小值,并将值存储在数组a []中的当前索引处。
  4. 同样,遍历以查找数组当前窗口的最小元素,并将最小值存储在变量中以存储当前窗口的最小值。
  5. 检查当前窗口的最小值的变量是否大于最小值的最大值的变量,将最小值的最大值的变量更新为当前窗口的最小值的变量。
  6. 打印最大最小值的变量。

C ++程序

#include <bits/stdc++.h> 
using namespace std; 
  
void printMaxOfMin(int a[], int n){ 
    
    for(int k=1; k<=n; k++){ 
        int maxOfMin = INT_MIN; 
  
        for(int i = 0; i <= n-k; i++){ 
            int min = a[i]; 
            for(int j = 1; j < k; j++){ 
                if(a[i+j] < min){ 
                    min = a[i+j]; 
                }
            } 
  
            if(min > maxOfMin){ 
              maxOfMin = min; 
            }
        } 
  
        cout << maxOfMin << " "; 
    } 
} 
  
int main(){ 
    int a[] = {10, 20, 30, 50, 10, 70, 30}; 
    int n = sizeof(a)/sizeof(a[0]); 
    
    printMaxOfMin(a, n); 
    
    return 0; 
}
70 30 20 10 10 10 10

Java程序

class MaxOfMin{
    
    static int a[] = {10, 20, 30, 50, 10, 70, 30}; 
      
    static void printMaxOfMin(int n){ 
        
        for(int k=1; k<=n; k++){ 
            int maxOfMin = Integer.MIN_VALUE; 
       
            for(int i = 0; i <= n-k; i++){ 
                int min = a[i]; 
                
                for(int j = 1; j < k; j++){ 
                    if(a[i+j] < min){ 
                        min = a[i+j];
                    }
                } 
       
                if(min > maxOfMin){ 
                    maxOfMin = min; 
                }
            } 
       
            System.out.print(maxOfMin + " "); 
        } 
    } 
      
    public static void main(String[] args){ 
        printMaxOfMin(a.length); 
    } 
}
70 30 20 10 10 10 10

复杂度分析,以找到每个窗口大小的最小值最大值

时间复杂度:3),其中n是给定数组a []中元素的数量。

辅助空间: O(1),因为我们使用了恒定的额外空间。

查找每个窗口大小的最小值最大值的有效方法

算法

  1. 初始化大小为n的数组a []。
  2. 创建一个 数据结构和长度为n + 2的左右两个数组。 遍历并将左数组的所有值设置为-1,将右数组的所有值设置为n。
  3. 从0遍历到n-1,并且当堆栈不为空并且索引处的数组a []中的值等于堆栈的顶部时,大于或等于当前索引处的数组a []中的值,请弹出元素位于堆栈顶部。
  4. 如果堆栈不为空,则更新堆栈顶部左侧数组中当前索引处的值。 将当前索引压入堆栈。
  5. 当堆栈不为空时,将元素弹出堆栈顶部。
  6. 同样,从n-1遍历到0,并且当堆栈不为空并且索引处的数组a []中的值等于堆栈顶部时,则大于或等于当前索引处的数组a []中的值,在堆栈顶部弹出该元素。
  7. 如果堆栈不为空,则在堆栈顶部右边的数组中更新当前索引处的值。 将当前索引压入堆栈。
  8. 创建另一个大小为n + 1的数组以存储答案,并将其所有值设置为0。
  9. 从0遍历到n-1,并在左右数组的当前索引处找到值之间的窗口长度,并将答案数组更新为a []的当前索引处和等于索引处的值的最大值到答案数组的计算间隔。
  10. 打印答案数组。

C ++程序

#include <bits/stdc++.h> 
using namespace std; 
  
void printMaxOfMin(int a[], int n){ 
    
    stack<int> s;  
  
    int left[n+1];   
    int right[n+1];  
  
    for(int i=0; i<n; i++){ 
        left[i] = -1; 
        right[i] = n; 
    } 
  
    for(int i=0; i<n; i++){ 
        while(!s.empty() && a[s.top()] >= a[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            left[i] = s.top();
        }
  
        s.push(i); 
    } 
  
    while(!s.empty()){ 
        s.pop(); 
    }
  
    for(int i = n-1 ; i>=0 ; i--){ 
        while(!s.empty() && a[s.top()] >= a[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            right[i] = s.top(); 
        }
  
        s.push(i); 
    } 
  
    int ans[n+1]; 
    for(int i=0; i<=n; i++){ 
        ans[i] = 0; 
    }
  
    for(int i=0; i<n; i++){ 
        int len = right[i] - left[i] - 1; 
  
        ans[len] = max(ans[len], a[i]); 
    } 
  
    for(int i=n-1; i>=1; i--){ 
        ans[i] = max(ans[i], ans[i+1]);
    }
  
    for(int i=1; i<=n; i++){ 
        cout << ans[i] << " ";
    }
} 
  
int main(){ 
    int a[] = {10, 20, 30, 50, 10, 70, 30}; 
    int n = sizeof(a)/sizeof(a[0]); 
    
    printMaxOfMin(a, n); 
    
    return 0; 
}
70 30 20 10 10 10 10

Java程序

import java.util.Stack;

class MaxOfMin{
    
    static int a[] = {10, 20, 30, 50, 10, 70, 30}; 
      
    static void printMaxOfMin(int n){ 
        
        Stack<Integer> s = new Stack<>(); 
       
        int left[] = new int[n+1];   
        int right[]  = new int[n+1];  
       
        for(int i=0; i<n; i++){ 
            left[i] = -1; 
            right[i] = n; 
        } 
       
        for(int i=0; i<n; i++){ 
            while(!s.empty() && a[s.peek()] >= a[i]){ 
                s.pop(); 
            }
       
            if(!s.empty()){ 
                left[i] = s.peek();
            }
       
            s.push(i); 
        } 
       
        while(!s.empty()){ 
            s.pop(); 
        }
       
        for(int i = n-1 ; i>=0 ; i--){ 
            while(!s.empty() && a[s.peek()] >= a[i]){ 
                s.pop(); 
            }
       
            if(!s.empty()){ 
                right[i] = s.peek(); 
            }
       
            s.push(i); 
        } 
       
        int ans[] = new int[n+1]; 
        for(int i=0; i<=n; i++){ 
            ans[i] = 0; 
        }
       
        for(int i=0; i<n; i++){ 
            int len = right[i] - left[i] - 1; 
            ans[len] = Math.max(ans[len], a[i]); 
        } 
       
        for(int i=n-1; i>=1; i--){ 
            ans[i] = Math.max(ans[i], ans[i+1]);
        }
       
        for(int i=1; i<=n; i++){ 
            System.out.print(ans[i] + " "); 
        }
    } 
      
    public static void main(String[] args){ 
        printMaxOfMin(a.length); 
    } 
}
70 30 20 10 10 10 10

复杂度分析,以找到每个窗口大小的最小值最大值

时间复杂度: O(n)其中n是给定数组a []中元素的数量。

辅助空间: O(n),因为我们将堆栈空间用于n个元素。

參考資料