给定一个大小为n的整数数组，找出数组中每个窗口大小的最小值中的最大值。请注意，窗口大小从1到n不等。 例子：
null
输入：arr[]={10,20,30,50,10,70,30} 输出：70,30,20,10,10,10,10 输出中的第一个元素表示所有元素的最大值和最小值 大小为1的窗户。 大小为1的窗口的最小值为{10}、{20}、{30}、{50}、{10}， {70}和{30}。这些最小值的最大值为70 输出中的第二个元素表示所有元素的最大值和最小值 2号窗户。 大小为2的窗口的最小值为{10}，{20}，{30}，{10}，{10}， 和{30}。这些最小值的最大值为30 输出中的第三个元素表示所有元素的最大值和最小值 3号窗户。 大小为3的窗口的最小值为{10}、{20}、{10}、{10}和{10}。 这些最小值的最大值为20 类似地，也会计算输出的其他元素。
天真的解决方案 : 蛮力。 方法： 解决这个问题的一个简单的暴力方法是生成所有可能的特定长度的窗口，比如“L”，并在所有这些窗口中找到最小元素。然后找到所有这些元素的最大值并存储。现在窗口的长度是1<=L<=N。所以我们必须生成大小为“1”到“N”的所有可能窗口，并且为了生成每个这样的窗口，我们必须标记该窗口的端点。因此，我们必须使用嵌套循环来分别固定窗口的起点和终点。因此，在蛮力方法中会使用三重嵌套循环，主要用于固定窗口的长度、起点和终点。
C++
// A naive method to find maximum of // minimum of all windows of different // sizes #include <bits/stdc++.h> using namespace std; void printMaxOfMin( int arr[], int n) { // Consider all windows of different // sizes starting from size 1 for ( int k = 1; k <= n; k++) { // Initialize max of min for // current window size k int maxOfMin = INT_MIN; // Traverse through all windows // of current size k for ( int i = 0; i <= n - k; i++) { // Find minimum of current window int min = arr[i]; for ( int j = 1; j < k; j++) { if (arr[i + j] < min) min = arr[i + j]; } // Update maxOfMin if required if (min > maxOfMin) maxOfMin = min; } // Print max of min for current // window size cout << maxOfMin << " " ; } } // Driver program int main() { int arr[] = { 10, 20, 30, 50, 10, 70, 30 }; int n = sizeof (arr) / sizeof (arr[0]); printMaxOfMin(arr, n); return 0; } |
JAVA
// A naive method to find maximum of // minimum of all windows of different sizes class Test { static int arr[] = { 10 , 20 , 30 , 50 , 10 , 70 , 30 }; static void printMaxOfMin( int n) { // Consider all windows of different // sizes starting from size 1 for ( int k = 1 ; k <= n; k++) { // Initialize max of min for current // window size k int maxOfMin = Integer.MIN_VALUE; // Traverse through all windows of // current size k for ( int i = 0 ; i <= n - k; i++) { // Find minimum of current window int min = arr[i]; for ( int j = 1 ; j < k; j++) { if (arr[i + j] < min) min = arr[i + j]; } // Update maxOfMin if required if (min > maxOfMin) maxOfMin = min; } // Print max of min for current // window size System.out.print(maxOfMin + " " ); } } // Driver method public static void main(String[] args) { printMaxOfMin(arr.length); } } |
Python3
# A naive method to find maximum of # minimum of all windows of different sizes INT_MIN = - 1000000 def printMaxOfMin(arr, n): # Consider all windows of different # sizes starting from size 1 for k in range ( 1 , n + 1 ): # Initialize max of min for # current window size k maxOfMin = INT_MIN; # Traverse through all windows # of current size k for i in range (n - k + 1 ): # Find minimum of current window min = arr[i] for j in range (k): if (arr[i + j] < min ): min = arr[i + j] # Update maxOfMin if required if ( min > maxOfMin): maxOfMin = min # Print max of min for current window size print (maxOfMin, end = " " ) # Driver Code arr = [ 10 , 20 , 30 , 50 , 10 , 70 , 30 ] n = len (arr) printMaxOfMin(arr, n) # This code is contributed by sahilshelangia |
C#
// C# program using Naive approach to find // maximum of minimum of all windows of // different sizes using System; class GFG{ static int []arr = {10, 20, 30, 50, 10, 70, 30}; // Function to print maximum of minimum static void printMaxOfMin( int n) { // Consider all windows of different // sizes starting from size 1 for ( int k = 1; k <= n; k++) { // Initialize max of min for // current window size k int maxOfMin = int .MinValue; // Traverse through all windows // of current size k for ( int i = 0; i <= n - k; i++) { // Find minimum of current window int min = arr[i]; for ( int j = 1; j < k; j++) { if (arr[i + j] < min) min = arr[i + j]; } // Update maxOfMin if required if (min > maxOfMin) maxOfMin = min; } // Print max of min for current window size Console.Write(maxOfMin + " " ); } } // Driver Code public static void Main() { printMaxOfMin(arr.Length); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to find maximum of // minimum of all windows of // different sizes // Method to find maximum of // minimum of all windows of // different sizes function printMaxOfMin( $arr , $n ) { // Consider all windows of // different sizes starting // from size 1 for ( $k = 1; $k <= $n ; $k ++) { // Initialize max of min for // current window size k $maxOfMin = PHP_INT_MIN; // Traverse through all windows // of current size k for ( $i = 0; $i <= $n - $k ; $i ++) { // Find minimum of current window $min = $arr [ $i ]; for ( $j = 1; $j < $k ; $j ++) { if ( $arr [ $i + $j ] < $min ) $min = $arr [ $i + $j ]; } // Update maxOfMin // if required if ( $min > $maxOfMin ) $maxOfMin = $min ; } // Print max of min for // current window size echo $maxOfMin , " " ; } } // Driver Code $arr = array (10, 20, 30, 50, 10, 70, 30); $n = sizeof( $arr ); printMaxOfMin( $arr , $n ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // A naive method to find maximum of // minimum of all windows of different sizes var arr = [ 10, 20, 30, 50, 10, 70, 30 ]; function printMaxOfMin(n) { // Consider all windows of different // sizes starting from size 1 for (k = 1; k <= n; k++) { // Initialize max of min for current // window size k var maxOfMin = Number.MIN_VALUE; // Traverse through all windows of // current size k for (i = 0; i <= n - k; i++) { // Find minimum of current window var min = arr[i]; for (j = 1; j < k; j++) { if (arr[i + j] < min) min = arr[i + j]; } // Update maxOfMin if required if (min > maxOfMin) maxOfMin = min; } // Print max of min for current // window size document.write(maxOfMin + " " ); } } // Driver method printMaxOfMin(arr.length); // This code contributed by aashish1995 </script> |
输出：
70 30 20 10 10 10 10
复杂性分析：
- 时间复杂性： O（n） 3. ). 因为在这种方法中使用了三重嵌套循环。
- 辅助空间： O（1） 因为没有使用额外的数据结构来存储这些值。
有效解决方案 : 我们能及时解决这个问题。这个想法是使用额外的空间。下面是详细的步骤。 第一步： 为每个元素查找下一个较小的和上一个较小的索引。下一个较小的元素是arr[i]右侧最近的最小元素。类似地，前面较小的元素是arr[i]左侧最近的最小元素。 如果右侧没有较小的元素，则下一个较小的元素为n。如果左侧没有较小的元素，则上一个较小的元素为-1。 对于输入{10,20,30,50,10,70,30}，下一个较小的索引数组是{7,4,4,7,6,7}。 对于输入{10,20,30,50,10,70,30}，先前较小的索引数组是{-1,0,1,2，-1,4,4} 使用中讨论的方法，这一步可以在O（n）时间内完成 下一个更大的元素 . 第二步： 一旦我们有了next和previous较小的索引，我们就知道arr[i]是长度为“right[i]–left[i]–1”的窗口的最小值。元素最小的窗口长度为{7,3,2,1,7,1,2}。该数组表示，第一个元素在大小为7的窗口中最小，第二个元素在大小为3的窗口中最小，依此类推。 创建一个辅助数组ans[n+1]来存储结果。ans[]中的值可以通过迭代右[]和左[]来填充
for (int i=0; i < n; i++) { // length of the interval int len = right[i] - left[i] - 1; // arr[i] is a possible answer for // this length len interval ans[len] = max(ans[len], arr[i]); }
我们得到ans[]数组为{0,70,30,20,0,0,0,10}。请注意，长度为0的ans[0]或答案是无用的。 第三步： ans[]中的某些条目为0，尚未填写。例如，我们知道长度1、2、3和7的最大最小值分别为70、30、20和10，但我们不知道长度4、5和6的最大最小值相同。 下面是一些重要的观察结果，以填补剩余的条目 a） 长度i的结果，即ans[i]总是大于或等于长度i+1的结果，即ans[i+1]。 b） 如果ans[i]未填充，则意味着不存在长度i最小的直接元素，因此长度ans[i+1]或ans[i+2]等元素与ans[i]相同 所以我们使用下面的循环来填充其余的条目。
for (int i=n-1; i>=1; i--) ans[i] = max(ans[i], ans[i+1]);
下面是上述算法的实现。
C++
// An efficient C++ program to find // maximum of all minimums of // windows of different sizes #include <iostream> #include<stack> using namespace std; void printMaxOfMin( int arr[], int n) { // Used to find previous and next smaller stack< int > s; // Arrays to store previous and next smaller int left[n+1]; int right[n+1]; // Initialize elements of left[] and right[] for ( int i=0; i<n; i++) { left[i] = -1; right[i] = n; } // Fill elements of left[] using logic discussed on for ( int i=0; i<n; i++) { while (!s.empty() && arr[s.top()] >= arr[i]) s.pop(); if (!s.empty()) left[i] = s.top(); s.push(i); } // Empty the stack as stack is // going to be used for right[] while (!s.empty()) s.pop(); // Fill elements of right[] using same logic for ( int i = n-1 ; i>=0 ; i-- ) { while (!s.empty() && arr[s.top()] >= arr[i]) s.pop(); if (!s.empty()) right[i] = s.top(); s.push(i); } // Create and initialize answer array int ans[n+1]; for ( int i=0; i<=n; i++) ans[i] = 0; // Fill answer array by comparing minimums of all // lengths computed using left[] and right[] for ( int i=0; i<n; i++) { // length of the interval int len = right[i] - left[i] - 1; // arr[i] is a possible answer for this length // 'len' interval, check if arr[i] is more than // max for 'len' ans[len] = max(ans[len], arr[i]); } // Some entries in ans[] may not be filled yet. Fill // them by taking values from right side of ans[] for ( int i=n-1; i>=1; i--) ans[i] = max(ans[i], ans[i+1]); // Print the result for ( int i=1; i<=n; i++) cout << ans[i] << " " ; } // Driver program int main() { int arr[] = {10, 20, 30, 50, 10, 70, 30}; int n = sizeof (arr)/ sizeof (arr[0]); printMaxOfMin(arr, n); return 0; } |
JAVA
// An efficient Java program to find // maximum of all minimums of // windows of different size import java.util.Stack; class Test { static int arr[] = { 10 , 20 , 30 , 50 , 10 , 70 , 30 }; static void printMaxOfMin( int n) { // Used to find previous and next smaller Stack<Integer> s = new Stack<>(); // Arrays to store previous and next smaller int left[] = new int [n+ 1 ]; int right[] = new int [n+ 1 ]; // Initialize elements of left[] and right[] for ( int i= 0 ; i<n; i++) { left[i] = - 1 ; right[i] = n; } // Fill elements of left[] using logic discussed on for ( int i= 0 ; i<n; i++) { while (!s.empty() && arr[s.peek()] >= arr[i]) s.pop(); if (!s.empty()) left[i] = s.peek(); s.push(i); } // Empty the stack as stack is // going to be used for right[] while (!s.empty()) s.pop(); // Fill elements of right[] using same logic for ( int i = n- 1 ; i>= 0 ; i-- ) { while (!s.empty() && arr[s.peek()] >= arr[i]) s.pop(); if (!s.empty()) right[i] = s.peek(); s.push(i); } // Create and initialize answer array int ans[] = new int [n+ 1 ]; for ( int i= 0 ; i<=n; i++) ans[i] = 0 ; // Fill answer array by comparing minimums of all // lengths computed using left[] and right[] for ( int i= 0 ; i<n; i++) { // length of the interval int len = right[i] - left[i] - 1 ; // arr[i] is a possible answer for this length // 'len' interval, check if arr[i] is more than // max for 'len' ans[len] = Math.max(ans[len], arr[i]); } // Some entries in ans[] may not be filled yet. Fill // them by taking values from right side of ans[] for ( int i=n- 1 ; i>= 1 ; i--) ans[i] = Math.max(ans[i], ans[i+ 1 ]); // Print the result for ( int i= 1 ; i<=n; i++) System.out.print(ans[i] + " " ); } // Driver method public static void main(String[] args) { printMaxOfMin(arr.length); } } |
Python3
# An efficient Python3 program to find # maximum of all minimums of windows of # different sizes def printMaxOfMin(arr, n): s = [] # Used to find previous # and next smaller # Arrays to store previous and next # smaller. Initialize elements of # left[] and right[] left = [ - 1 ] * (n + 1 ) right = [n] * (n + 1 ) # Fill elements of left[] using logic discussed on # https:#www.geeksforgeeks.org/next-greater-element for i in range (n): while ( len (s) ! = 0 and arr[s[ - 1 ]] > = arr[i]): s.pop() if ( len (s) ! = 0 ): left[i] = s[ - 1 ] s.append(i) # Empty the stack as stack is going # to be used for right[] while ( len (s) ! = 0 ): s.pop() # Fill elements of right[] using same logic for i in range (n - 1 , - 1 , - 1 ): while ( len (s) ! = 0 and arr[s[ - 1 ]] > = arr[i]): s.pop() if ( len (s) ! = 0 ): right[i] = s[ - 1 ] s.append(i) # Create and initialize answer array ans = [ 0 ] * (n + 1 ) for i in range (n + 1 ): ans[i] = 0 # Fill answer array by comparing minimums # of all. Lengths computed using left[] # and right[] for i in range (n): # Length of the interval Len = right[i] - left[i] - 1 # arr[i] is a possible answer for this # Length 'Len' interval, check if arr[i] # is more than max for 'Len' ans[ Len ] = max (ans[ Len ], arr[i]) # Some entries in ans[] may not be filled # yet. Fill them by taking values from # right side of ans[] for i in range (n - 1 , 0 , - 1 ): ans[i] = max (ans[i], ans[i + 1 ]) # Print the result for i in range ( 1 , n + 1 ): print (ans[i], end = " " ) # Driver Code if __name__ = = '__main__' : arr = [ 10 , 20 , 30 , 50 , 10 , 70 , 30 ] n = len (arr) printMaxOfMin(arr, n) # This code is contributed by PranchalK |
C#
// An efficient C# program to find maximum // of all minimums of windows of different size using System; using System.Collections.Generic; class GFG { public static int [] arr = new int [] {10, 20, 30, 50, 10, 70, 30}; public static void printMaxOfMin( int n) { // Used to find previous and next smaller Stack< int > s = new Stack< int >(); // Arrays to store previous // and next smaller int [] left = new int [n + 1]; int [] right = new int [n + 1]; // Initialize elements of left[] // and right[] for ( int i = 0; i < n; i++) { left[i] = -1; right[i] = n; } // Fill elements of left[] using logic discussed on for ( int i = 0; i < n; i++) { while (s.Count > 0 && arr[s.Peek()] >= arr[i]) { s.Pop(); } if (s.Count > 0) { left[i] = s.Peek(); } s.Push(i); } // Empty the stack as stack is going // to be used for right[] while (s.Count > 0) { s.Pop(); } // Fill elements of right[] using // same logic for ( int i = n - 1 ; i >= 0 ; i--) { while (s.Count > 0 && arr[s.Peek()] >= arr[i]) { s.Pop(); } if (s.Count > 0) { right[i] = s.Peek(); } s.Push(i); } // Create and initialize answer array int [] ans = new int [n + 1]; for ( int i = 0; i <= n; i++) { ans[i] = 0; } // Fill answer array by comparing // minimums of all lengths computed // using left[] and right[] for ( int i = 0; i < n; i++) { // length of the interval int len = right[i] - left[i] - 1; // arr[i] is a possible answer for // this length 'len' interval, check x // if arr[i] is more than max for 'len' ans[len] = Math.Max(ans[len], arr[i]); } // Some entries in ans[] may not be // filled yet. Fill them by taking // values from right side of ans[] for ( int i = n - 1; i >= 1; i--) { ans[i] = Math.Max(ans[i], ans[i + 1]); } // Print the result for ( int i = 1; i <= n; i++) { Console.Write(ans[i] + " " ); } } // Driver Code public static void Main( string [] args) { printMaxOfMin(arr.Length); } } // This code is contributed by Shrikant13 |
Javascript
<script> // An efficient Javascript program to find maximum // of all minimums of windows of different size let arr = [10, 20, 30, 50, 10, 70, 30]; function printMaxOfMin(n) { // Used to find previous and next smaller let s = []; // Arrays to store previous // and next smaller let left = new Array(n + 1); left.fill(0); let right = new Array(n + 1); right.fill(0); // Initialize elements of left[] // and right[] for (let i = 0; i < n; i++) { left[i] = -1; right[i] = n; } // Fill elements of left[] using logic discussed on for (let i = 0; i < n; i++) { while (s.length > 0 && arr[s[s.length - 1]] >= arr[i]) { s.pop(); } if (s.length > 0) { left[i] = s[s.length - 1]; } s.push(i); } // Empty the stack as stack is going // to be used for right[] while (s.length > 0) { s.pop(); } // Fill elements of right[] using // same logic for (let i = n - 1 ; i >= 0 ; i--) { while (s.length > 0 && arr[s[s.length - 1]] >= arr[i]) { s.pop(); } if (s.length > 0) { right[i] = s[s.length - 1]; } s.push(i); } // Create and initialize answer array let ans = new Array(n + 1); ans.fill(0); for (let i = 0; i <= n; i++) { ans[i] = 0; } // Fill answer array by comparing // minimums of all lengths computed // using left[] and right[] for (let i = 0; i < n; i++) { // length of the interval let len = right[i] - left[i] - 1; // arr[i] is a possible answer for // this length 'len' interval, check x // if arr[i] is more than max for 'len' ans[len] = Math.max(ans[len], arr[i]); } // Some entries in ans[] may not be // filled yet. Fill them by taking // values from right side of ans[] for (let i = n - 1; i >= 1; i--) { ans[i] = Math.max(ans[i], ans[i + 1]); } // Print the result for (let i = 1; i <= n; i++) { document.write(ans[i] + " " ); } } printMaxOfMin(arr.length); // This code is contributed by decode2207. </script> |
输出：
70 30 20 10 10 10 10
复杂性分析：
- 时间复杂性： O（n）。 这种方法中的每个子任务都需要线性时间。
- 辅助空间： O（n）。 使用堆栈计算下一个最小值，并使用数组存储中间结果。
本文由 埃克塔·戈尔 和 阿尤什·戈维尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
