给定一个数组arr[]，求最大j–i，使arr[j]>arr[i]。
null
例如：
Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Input: {1, 2, 3, 4, 5, 6} Output: 5 (j = 5, i = 0) Input: {6, 5, 4, 3, 2, 1} Output: -1
方法1（简单但低效） 运行两个循环。在外部循环中，从左侧逐个拾取元素。在内部循环中，将拾取的图元与从右侧开始的图元进行比较。当看到一个元素大于拾取的元素时，停止内部循环，并继续更新到目前为止的最大j-i。
C++
// CPP program for the above approach #include <bits/stdc++.h> using namespace std; /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n - 1; j > i; --j) { if (arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) / sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); cout << "" << maxDiff; return 0; } // This code is contributed // by Akanksha Rai(Abby_akku) |
C
// C program for the above approach #include <stdio.h> /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n - 1; j > i; --j) { if (arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) / sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); printf ( " %d" , maxDiff); getchar (); return 0; } |
JAVA
// Java program for the above approach class FindMaximum { /* For a given array arr[], returns the maximum j-i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff = - 1 ; int i, j; for (i = 0 ; i < n; ++i) { for (j = n - 1 ; j > i; --j) { if (arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } /* Driver program to test above functions */ public static void main(String[] args) { FindMaximum max = new FindMaximum(); int arr[] = { 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 }; int n = arr.length; int maxDiff = max.maxIndexDiff(arr, n); System.out.println(maxDiff); } } |
Python3
# Python3 program to find the maximum # j – i such that arr[j] > arr[i] # For a given array arr[], returns # the maximum j – i such that # arr[j] > arr[i] def maxIndexDiff(arr, n): maxDiff = - 1 for i in range ( 0 , n): j = n - 1 while (j > i): if arr[j] > arr[i] and maxDiff < (j - i): maxDiff = j - i j - = 1 return maxDiff # driver code arr = [ 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 ] n = len (arr) maxDiff = maxIndexDiff(arr, n) print (maxDiff) # This article is contributed by Smitha Dinesh Semwal |
C#
// C# program to find the maximum // j – i such that arr[j] > arr[i] using System; class GFG { // For a given array arr[], returns // the maximum j-i such that arr[j] > arr[i] static int maxIndexDiff( int [] arr, int n) { int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n - 1; j > i; --j) { if (arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } // Driver program public static void Main() { int [] arr = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = arr.Length; int maxDiff = maxIndexDiff(arr, n); Console.Write(maxDiff); } } // This Code is Contributed by Sam007 |
PHP
<?php // PHP program to find the maximum // j – i such that arr[j] > arr[i] // For a given array arr[], returns // the maximum j – i such that // arr[j] > arr[i] function maxIndexDiff( $arr , $n ) { $maxDiff = -1; for ( $i = 0; $i < $n ; ++ $i ) { for ( $j = $n - 1; $j > $i ; -- $j ) { if ( $arr [ $j ] > $arr [ $i ] && $maxDiff < ( $j - $i )) $maxDiff = $j - $i ; } } return $maxDiff ; } // Driver Code $arr = array (9, 2, 3, 4, 5, 6, 7, 8, 18, 0); $n = count ( $arr ); $maxDiff = maxIndexDiff( $arr , $n ); echo $maxDiff ; // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript program for the above approach /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ function maxIndexDiff(arr, n) { let maxDiff = -1; let i, j; for (i = 0; i < n; ++i) { for (j = n - 1; j > i; --j) { if (arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff; } // Driver code let arr = [ 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 ]; let n = arr.length; let maxDiff = maxIndexDiff(arr, n); document.write(maxDiff); // This code is contributed by Manoj. </script> |
输出
8
时间复杂性： O（n^2）
方法2- 即兴使用蛮力算法，寻找BUD，即瓶颈、不必要和重复的作品。快速观察实际上表明，我们一直在寻找从数组末尾到当前索引的第一个最大元素。我们可以看到，我们正在一次又一次地为数组中的每个元素寻找第一个最大的元素。假设我们有一个数组，例如[1,5,12,4,9]，现在我们知道9是大于1,5,4的元素，但是为什么我们需要一次又一次地找到它呢。实际上，我们可以跟踪从数组末尾到数组开头移动的最大数量。这种方法将帮助我们更好地理解，而且这种即兴创作在面试中也很好。
方法：
- 从末尾遍历数组，并跟踪当前索引（包括self）右侧的最大数量
- 现在我们有了一个单调递减的数组，我们知道我们可以使用二进制搜索来找到最右边的大元素的索引
- 现在我们将对数组中的每个元素使用二进制搜索，并存储索引的最大差异，就这样完成了。
C++
/* For a given array arr[], calculates the maximum j – i such that arr[j] > arr[i] */ #include <bits/stdc++.h> using namespace std; int main() { vector< long long int > v{ 34, 8, 10, 3, 2, 80, 30, 33, 1 }; int n = v.size(); vector< long long int > maxFromEnd(n + 1, INT_MIN); // create an array maxfromEnd for ( int i = v.size() - 1; i >= 0; i--) { maxFromEnd[i] = max(maxFromEnd[i + 1], v[i]); } int result = 0; for ( int i = 0; i < v.size(); i++) { int low = i + 1, high = v.size() - 1, ans = i; while (low <= high) { int mid = (low + high) / 2; if (v[i] <= maxFromEnd[mid]) { // We store this as current answer and look // for further larger number to the right // side ans = max(ans, mid); low = mid + 1; } else { high = mid - 1; } } // keeping a track of the // maximum difference in indices result = max(result, ans - i); } cout << result << endl; } |
JAVA
// Java program to implement // the above approach // For a given array arr[], // calculates the maximum j – i // such that arr[j] > arr[i] import java.util.*; class GFG{ public static void main(String[] args) { int []v = { 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 }; int n = v.length; int []maxFromEnd = new int [n + 1 ]; Arrays.fill(maxFromEnd, Integer.MIN_VALUE); // Create an array maxfromEnd for ( int i = v.length - 1 ; i >= 0 ; i--) { maxFromEnd[i] = Math.max(maxFromEnd[i + 1 ], v[i]); } int result = 0 ; for ( int i = 0 ; i < v.length; i++) { int low = i + 1 , high = v.length - 1 , ans = i; while (low <= high) { int mid = (low + high) / 2 ; if (v[i] <= maxFromEnd[mid]) { // We store this as current // answer and look for further // larger number to the right side ans = Math.max(ans, mid); low = mid + 1 ; } else { high = mid - 1 ; } } // Keeping a track of the // maximum difference in indices result = Math.max(result, ans - i); } System.out.print(result + "" ); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program to implement # the above approach # For a given array arr, # calculates the maximum j – i # such that arr[j] > arr[i] # Driver code if __name__ = = '__main__' : v = [ 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 ]; n = len (v); maxFromEnd = [ - 38749432 ] * (n + 1 ); # Create an array maxfromEnd for i in range (n - 1 , 0 , - 1 ): maxFromEnd[i] = max (maxFromEnd[i + 1 ], v[i]); result = 0 ; for i in range ( 0 , n): low = i + 1 ; high = n - 1 ; ans = i; while (low < = high): mid = int ((low + high) / 2 ); if (v[i] < = maxFromEnd[mid]): # We store this as current # answer and look for further # larger number to the right side ans = max (ans, mid); low = mid + 1 ; else : high = mid - 1 ; # Keeping a track of the # maximum difference in indices result = max (result, ans - i); print (result, end = ""); # This code is contributed by Rajput-Ji |
C#
// C# program to implement // the above approach // For a given array []arr, // calculates the maximum j – i // such that arr[j] > arr[i] using System; class GFG{ public static void Main(String[] args) { int []v = {34, 8, 10, 3, 2, 80, 30, 33, 1}; int n = v.Length; int []maxFromEnd = new int [n + 1]; for ( int i = 0; i < maxFromEnd.Length; i++) maxFromEnd[i] = int .MinValue; // Create an array maxfromEnd for ( int i = v.Length - 1; i >= 0; i--) { maxFromEnd[i] = Math.Max(maxFromEnd[i + 1], v[i]); } int result = 0; for ( int i = 0; i < v.Length; i++) { int low = i + 1, high = v.Length - 1, ans = i; while (low <= high) { int mid = (low + high) / 2; if (v[i] <= maxFromEnd[mid]) { // We store this as current // answer and look for further // larger number to the right side ans = Math.Max(ans, mid); low = mid + 1; } else { high = mid - 1; } } // Keeping a track of the // maximum difference in indices result = Math.Max(result, ans - i); } Console.Write(result + "" ); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // For a given array []arr, // calculates the maximum j – i // such that arr[j] > arr[i] let v = [34, 8, 10, 3, 2, 80, 30, 33, 1]; let n = v.length; let maxFromEnd = new Array(n + 1); for (let i = 0; i < maxFromEnd.length; i++) maxFromEnd[i] = Number.MIN_VALUE; // Create an array maxfromEnd for (let i = v.length - 1; i >= 0; i--) { maxFromEnd[i] = Math.max(maxFromEnd[i + 1], v[i]); } let result = 0; for (let i = 0; i < v.length; i++) { let low = i + 1, high = v.length - 1, ans = i; while (low <= high) { let mid = parseInt((low + high) / 2, 10); if (v[i] <= maxFromEnd[mid]) { // We store this as current // answer and look for further // larger number to the right side ans = Math.max(ans, mid); low = mid + 1; } else { high = mid - 1; } } // Keeping a track of the // maximum difference in indices result = Math.max(result, ans - i); } document.write(result); </script> |
输出
6
时间复杂性： O（N*log（N）） 空间复杂性： O（N）
方法3 O（nLgn）： 在特别注意重复项之后，使用哈希和排序以低于二次复杂度的方式解决这个问题。 方法：
- 遍历数组并将每个元素的索引存储在列表中（以处理重复项）。
- 对数组进行排序。
- 现在遍历数组并跟踪i和j的最大差值。
- 对于j，从元素的可能索引列表中考虑最后一个索引，并且考虑列表中的第一个索引。（因为索引是按升序追加的）。
- 不断更新最大差值，直到数组结束。
C++
// C++ implementation of // the hashmap approach #include <bits/stdc++.h> using namespace std; // Function to find maximum // index difference int maxIndexDiff(vector< int >& arr, int n) { // Initialise unordered_map unordered_map< int , vector< int > > hashmap; // Iterate from 0 to n - 1 for ( int i = 0; i < n; i++) { hashmap[arr[i]].push_back(i); } // Sort arr sort(arr.begin(), arr.end()); int maxDiff = INT_MIN; int temp = n; // Iterate from 0 to n - 1 for ( int i = 0; i < n; i++) { if (temp > hashmap[arr[i]][0]) { temp = hashmap[arr[i]][0]; } maxDiff = max( maxDiff, hashmap[arr[i]][hashmap[arr[i]].size() - 1] - temp); } return maxDiff; } // Driver Code int main() { int n = 9; vector< int > arr{ 34, 8, 10, 3, 2, 80, 30, 33, 1 }; // Function Call int ans = maxIndexDiff(arr, n); cout << "The maxIndexDiff is : " << ans << endl; return 1; } |
JAVA
// Java implementation of // the hashmap approach import java.io.*; import java.util.*; class GFG{ // Function to find maximum // index difference static int maxIndexDiff(ArrayList<Integer> arr, int n) { // Initialise unordered_map Map<Integer, ArrayList<Integer>> hashmap = new HashMap<Integer, ArrayList<Integer>>(); // Iterate from 0 to n - 1 for ( int i = 0 ; i < n; i++) { if (hashmap.containsKey(arr.get(i))) { hashmap.get(arr.get(i)).add(i); } else { hashmap.put(arr.get(i), new ArrayList<Integer>()); hashmap.get(arr.get(i)).add(i); } } // Sort arr Collections.sort(arr); int maxDiff = Integer.MIN_VALUE; int temp = n; // Iterate from 0 to n - 1 for ( int i = 0 ; i < n; i++) { if (temp > hashmap.get(arr.get(i)).get( 0 )) { temp = hashmap.get(arr.get(i)).get( 0 ); } maxDiff = Math.max(maxDiff, hashmap.get(arr.get(i)).get( hashmap.get(arr.get(i)).size() - 1 ) - temp); } return maxDiff; } // Driver Code public static void main(String[] args) { int n = 9 ; ArrayList<Integer> arr = new ArrayList<Integer>( Arrays.asList( 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 )); // Function Call int ans = maxIndexDiff(arr, n); System.out.println( "The maxIndexDiff is : " + ans); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation of the above approach n = 9 a = [ 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 ] # To store the index of an element. index = dict () for i in range (n): if a[i] in index: # append to list (for duplicates) index[a[i]].append(i) else : # if first occurrence index[a[i]] = [i] # sort the input array a.sort() maxDiff = 0 # Temporary variable to keep track of minimum i temp = n for i in range (n): if temp > index[a[i]][ 0 ]: temp = index[a[i]][ 0 ] maxDiff = max (maxDiff, index[a[i]][ - 1 ] - temp) print (maxDiff) |
C#
// C# implementation of // the hashmap approach using System; using System.Collections.Generic; public class GFG { // Function to find maximum // index difference static int maxIndexDiff(List< int > arr, int n) { Dictionary< int ,List< int >> hashmap = new Dictionary< int ,List< int >>(); // Iterate from 0 to n - 1 for ( int i = 0; i < n; i++) { if (hashmap.ContainsKey(arr[i])) { hashmap[arr[i]].Add(i); } else { hashmap.Add(arr[i], new List< int >()); hashmap[arr[i]].Add(i); } } // Sort arr arr.Sort(); int maxDiff = -1; int temp = n; // Iterate from 0 to n - 1 for ( int i = 0; i < n; i++) { if (temp > hashmap[arr[i]][0] ) { temp = hashmap[arr[i]][0]; } maxDiff = Math.Max(maxDiff,hashmap[arr[i]][hashmap[arr[i]].Count - 1]- temp); } return maxDiff; } // Driver Code static public void Main (){ int n = 9; List< int > arr = new List< int >(); arr.Add(34); arr.Add(8); arr.Add(10); arr.Add(3); arr.Add(2); arr.Add(80); arr.Add(30); arr.Add(33); arr.Add(1); // Function Call int ans = maxIndexDiff(arr, n); Console.WriteLine( "The maxIndexDiff is : " + ans ); } } // This code is contributed by rag2127. |
Javascript
<script> // JavaScript implementation of // the hashmap approach // Function to find maximum // index difference function maxIndexDiff(arr,n) { // Initialise map in JavaScript let hashmap = new Map() // Iterate from 0 to n - 1 for (let i = 0; i < n; i++) { hashmap[arr[i]] = hashmap[arr[i]] || [] hashmap[arr[i]].push(i) } // Sort arr arr.sort((a,b)=> (a - b)) let maxDiff = 0 let temp = n // Iterate from 0 to n - 1 for (let i = 0; i < n; i++) { if (temp > hashmap[arr[i]][0]) { temp = hashmap[arr[i]][0] } maxDiff = Math.max( maxDiff,hashmap[arr[i]][hashmap[arr[i]].length - 1]- temp ) } return maxDiff } // Driver Code let n = 9 const arr = [ 34, 8, 10, 3, 2, 80, 30, 33, 1 ] // Function Call let ans = maxIndexDiff(arr, n) document.write(`The maxIndexDiff is : ${ans}`) // This code is contributed by shinjanpatra </script> |
输出
The maxIndexDiff is : 6
时间复杂性： O（N*log（N））
方法4（高效） 为了解决这个问题，我们需要得到两个最优的ARR[]索引：左索引I和右索引j。对于元素ARR[i]，如果ARR[i]的左侧有比ARR[i]小的元素，则不需要考虑左索引的ARR[i]。类似地，如果ARR [j]右侧有较大的元素，那么我们不需要考虑这个j用于右索引。因此，我们构造了两个辅助数组LMin[]和RMax[]，使得LMin[i]在arr[i]的左侧保留最小的元素，包括arr[i]，而RMax[j]在arr[j]的右侧保留最大的元素，包括arr[j]。在构造这两个辅助数组之后，我们从左到右遍历这两个数组。在遍历LMin[]和RMax[]时，如果我们看到LMin[i]大于RMax[j]，那么我们必须在LMin[]（或do i++）中前进，因为LMin[i]左边的所有元素都大于或等于LMin[i]。否则，我们必须在RMax[j]中继续前进，以寻找更大的j–i值。
感谢celicom为这种方法提出了算法。
工作示例：
让我们考虑任何例子[ 7，3，1，8，9，10，4，5，6 ]。
maxRight是什么？
从右侧填充6是第一个元素，现在6>5，所以我们再次填充6，直到达到10>6：
[10 10 10 10 6 6]我是maxR
[7 3 1 1]这是明尔
现在我们来看看如何从这些答案中找到答案，以及它的证明！！！
让我们比较一下数组的第一个元素，现在我们看到10>7，
现在我们将maxR增加1，直到它小于7，即在指数5处
所以直到现在的答案是。5-0 = 5
现在我们增加minL，我们得到3，它小于6，所以我们增加maxR，直到它达到最后一个索引，答案变成8-1=7
所以我们看到了我们是如何得到正确答案的。
当我们需要最大差异j i时，使得席[i ]
在前面的提示中，创建两个数组，
首先，将存储元素之前出现的最小元素
第二，将存储元素之后出现的最大元素
遍历第二个数组，直到第二个数组中的元素大于或等于第一个数组，并存储索引差。如果它变小，遍历第一个数组，直到它再次变大。
并存储该索引差异的最大差异。
C++
#include <bits/stdc++.h> using namespace std; /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int * LMin = new int [( sizeof ( int ) * n)]; int * RMax = new int [( sizeof ( int ) * n)]; /* Construct LMin[] such that LMin[i] stores the minimum value from (arr[0], arr[1], ... arr[i]) */ LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n - 1] = arr[n - 1]; for (j = n - 2; j >= 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); /* Traverse both arrays from left to right to find optimum j - i. This process is similar to merge() of MergeSort */ i = 0, j = 0, maxDiff = -1; while (j < n && i < n) { if (LMin[i] <= RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff; } // Driver Code int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) / sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); cout << maxDiff; return 0; } // This code is contributed by rathbhupendra |
C
#include <stdio.h> /* Utility Functions to get max and minimum of two integers */ int max( int x, int y) { return x > y ? x : y; } int min( int x, int y) { return x < y ? x : y; } /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int * LMin = ( int *) malloc ( sizeof ( int ) * n); int * RMax = ( int *) malloc ( sizeof ( int ) * n); /* Construct LMin[] such that LMin[i] stores the minimum value from (arr[0], arr[1], ... arr[i]) */ LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n - 1] = arr[n - 1]; for (j = n - 2; j >= 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); /* Traverse both arrays from left to right to find optimum j - i This process is similar to merge() of MergeSort */ i = 0, j = 0, maxDiff = -1; while (j < n && i < n) { if (LMin[i] <= RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff; } /* Driver program to test above functions */ int main() { int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = sizeof (arr) / sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); printf ( " %d" , maxDiff); getchar (); return 0; } |
JAVA
class FindMaximum { /* Utility Functions to get max and minimum of two integers */ int max( int x, int y) { return x > y ? x : y; } int min( int x, int y) { return x < y ? x : y; } /* For a given array arr[], returns the maximum j-i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int maxDiff; int i, j; int RMax[] = new int [n]; int LMin[] = new int [n]; /* Construct LMin[] such that LMin[i] stores the minimum value from (arr[0], arr[1], ... arr[i]) */ LMin[ 0 ] = arr[ 0 ]; for (i = 1 ; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1 ]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n - 1 ] = arr[n - 1 ]; for (j = n - 2 ; j >= 0 ; --j) RMax[j] = max(arr[j], RMax[j + 1 ]); /* Traverse both arrays from left to right to find optimum j - i This process is similar to merge() of MergeSort */ i = 0 ; j = 0 ; maxDiff = - 1 ; while (j < n && i < n) { if (LMin[i] <= RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1 ; } else i = i + 1 ; } return maxDiff; } /* Driver program to test the above functions */ public static void main(String[] args) { FindMaximum max = new FindMaximum(); int arr[] = { 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 }; int n = arr.length; int maxDiff = max.maxIndexDiff(arr, n); System.out.println(maxDiff); } } |
Python3
# Utility Functions to get max # and minimum of two integers def max (a, b): if (a > b): return a else : return b def min (a, b): if (a < b): return a else : return b # For a given array arr[], # returns the maximum j - i # such that arr[j] > arr[i] def maxIndexDiff(arr, n): maxDiff = 0 ; LMin = [ 0 ] * n RMax = [ 0 ] * n # Construct LMin[] such that # LMin[i] stores the minimum # value from (arr[0], arr[1], # ... arr[i]) LMin[ 0 ] = arr[ 0 ] for i in range ( 1 , n): LMin[i] = min (arr[i], LMin[i - 1 ]) # Construct RMax[] such that # RMax[j] stores the maximum # value from (arr[j], arr[j + 1], # ..arr[n-1]) RMax[n - 1 ] = arr[n - 1 ] for j in range (n - 2 , - 1 , - 1 ): RMax[j] = max (arr[j], RMax[j + 1 ]); # Traverse both arrays from left # to right to find optimum j - i # This process is similar to # merge() of MergeSort i, j = 0 , 0 maxDiff = - 1 while (j < n and i < n): if (LMin[i] < = RMax[j]): maxDiff = max (maxDiff, j - i) j = j + 1 else : i = i + 1 return maxDiff # Driver Code if (__name__ = = '__main__' ): arr = [ 9 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 18 , 0 ] n = len (arr) maxDiff = maxIndexDiff(arr, n) print (maxDiff) # This code is contributed # by gautam karakoti |
C#
// C# program to find the maximum // j – i such that arr[j] > arr[i] using System; class GFG { // Utility Functions to get max // and minimum of two integers static int max( int x, int y) { return x > y ? x : y; } static int min( int x, int y) { return x < y ? x : y; } // For a given array arr[], returns // the maximum j-i such thatarr[j] > arr[i] static int maxIndexDiff( int [] arr, int n) { int maxDiff; int i, j; int [] RMax = new int [n]; int [] LMin = new int [n]; // Construct LMin[] such that LMin[i] // stores the minimum value // from (arr[0], arr[1], ... arr[i]) LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); // Construct RMax[] such that // RMax[j] stores the maximum value // from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1] = arr[n - 1]; for (j = n - 2; j >= 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); // Traverse both arrays from left // to right to find optimum j - i // This process is similar to merge() // of MergeSort i = 0; j = 0; maxDiff = -1; while (j < n && i < n) { if (LMin[i] <= RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff; } // Driver program public static void Main() { int [] arr = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; int n = arr.Length; int maxDiff = maxIndexDiff(arr, n); Console.Write(maxDiff); } } // This Code is Contributed by Sam007 |
PHP
<?php // PHP program to find the maximum // j – i such that arr[j] > arr[i] // For a given array arr[], // returns the maximum j - i // such that arr[j] > arr[i] function maxIndexDiff( $arr , $n ) { $maxDiff = 0; $LMin = array_fill (0, $n , NULL); $RMax = array_fill (0, $n , NULL); // Construct LMin[] such that // LMin[i] stores the minimum // value from (arr[0], arr[1], // ... arr[i]) $LMin [0] = $arr [0]; for ( $i = 1; $i < $n ; $i ++) $LMin [ $i ] = min( $arr [ $i ], $LMin [ $i - 1]); // Construct RMax[] such that // RMax[j] stores the maximum // value from (arr[j], arr[j+1], // ..arr[n-1]) $RMax [ $n - 1] = $arr [ $n - 1]; for ( $j = $n - 2; $j >= 0; $j --) $RMax [ $j ] = max( $arr [ $j ], $RMax [ $j + 1]); // Traverse both arrays from left // to right to find optimum j - i // This process is similar to // merge() of MergeSort $i = 0; $j = 0; $maxDiff = -1; while ( $j < $n && $i < $n ) if ( $LMin [ $i ] <= $RMax [ $j ]) { $maxDiff = max( $maxDiff , $j - $i ); $j = $j + 1; } else $i = $i + 1; return $maxDiff ; } // Driver Code $arr = array (9, 2, 3, 4, 5, 6, 7, 8, 18, 0); $n = sizeof( $arr ); $maxDiff = maxIndexDiff( $arr , $n ); echo $maxDiff ; // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript program to find the maximum // j – i such that arr[j] > arr[i] // Utility Functions to get max // and minimum of two integers function max(x, y) { return x > y ? x : y; } function min(x, y) { return x < y ? x : y; } // For a given array arr[], returns // the maximum j-i such thatarr[j] > arr[i] function maxIndexDiff(arr, n) { let maxDiff; let i, j; let RMax = new Array(n); let LMin = new Array(n); // Construct LMin[] such that LMin[i] // stores the minimum value // from (arr[0], arr[1], ... arr[i]) LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i - 1]); // Construct RMax[] such that // RMax[j] stores the maximum value // from (arr[j], arr[j+1], ..arr[n-1]) RMax[n - 1] = arr[n - 1]; for (j = n - 2; j >= 0; --j) RMax[j] = max(arr[j], RMax[j + 1]); // Traverse both arrays from left // to right to find optimum j - i // This process is similar to merge() // of MergeSort i = 0; j = 0; maxDiff = -1; while (j < n && i < n) { if (LMin[i] <= RMax[j]) { maxDiff = max(maxDiff, j - i); j = j + 1; } else i = i + 1; } return maxDiff; } let arr = [ 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 ]; let n = arr.length; let maxDiff = maxIndexDiff(arr, n); document.write(maxDiff); </script> |
输出
8
时间复杂性： O（n） 辅助空间： O（n）
如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
另一种方法：（只使用一个额外的数组）
我们考虑一个辅助数组：RealMax []，这样，子阵ARR [ i（…n-1）]的右极大[i]＝max元素，是ARR [i]元素之后最大或相等的元素。
假设（arr[i]，arr[jLast]）是一对，使得arr[jLast]是比arr[i]大或相等的最后一个元素。对于以arr[jLast]结尾的对：（arr[k]，arr[jLast]），对于所有k=（i+1）到jLast
我们不需要考虑（jest-k）因为（jjas-i）>（jest-k）对于所有这样的K。
所以我们可以跳过这对。
从左到右遍历两个数组：arr[]和rightMax[]，当我们第一次遇到rightMax[j]
而且rightMax[]是非递增序列，所以rightMax[j]右侧的所有元素都小于或等于rightMax[j]。但是，在arr[i]（x>i）之后可能有arr[x]，因此，对于x>i，arr[x]
C++
#include <bits/stdc++.h> using namespace std; /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int rightMax[n]; rightMax[n-1]= arr[n-1]; for ( int i = n-2; i>=0; i--) rightMax[i] = max(rightMax[i+1] , arr[i]); //rightMax[i] = max{ arr[i...(n-1] } int maxDist = INT_MIN; int i = 0, j = 0; while (i<n && j<n) { if (rightMax[j] >= arr[i]) { maxDist = max( maxDist, j-i ); j++; } else // if(rightMax[j] < leftMin[i]) i++; } return maxDist; } // Driver Code int main() { int arr[] = { 34,8,10,3,2,80,30,33,1}; int n = sizeof (arr) / sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); cout << maxDiff; return 0; } // This code is contributed by Sourashis Mondal |
JAVA
import java.util.*; class GFG{ /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ static int maxIndexDiff( int arr[], int n) { int []rightMax = new int [n]; rightMax[n- 1 ]= arr[n- 1 ]; for ( int i = n- 2 ; i>= 0 ; i--) rightMax[i] = Math.max(rightMax[i+ 1 ] , arr[i]); // rightMax[i] = max{ arr[i...(n-1] } int maxDist = Integer.MIN_VALUE; int i = 0 , j = 0 ; while (i < n && j < n) { if (rightMax[j] >= arr[i]) { maxDist = Math.max( maxDist, j-i ); j++; } else // if(rightMax[j] < leftMin[i]) i++; } return maxDist; } // Driver Code public static void main(String[] args) { int arr[] = { 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 }; int n = arr.length; int maxDiff = maxIndexDiff(arr, n); System.out.print(maxDiff); } } // This code is contributed by Rajput-Ji |
Python3
# For a given array arr[], returns the # maximum j – i such that arr[j] > arr[i] def maxIndexDiff(arr, n): rightMax = [ 0 ] * n rightMax[n - 1 ] = arr[n - 1 ] for i in range (n - 2 , - 1 , - 1 ): rightMax[i] = max (rightMax[i + 1 ], arr[i]) # rightMax[i] = max arr[i...(n-1] maxDist = - 2 * * 31 i = 0 j = 0 while (i < n and j < n): if (rightMax[j] > = arr[i]): maxDist = max (maxDist, j - i) j + = 1 else : # if(rightMax[j] < leftMin[i]) i + = 1 return maxDist # Driver Code arr = [ 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 ] n = len (arr) maxDiff = maxIndexDiff(arr, n) print (maxDiff) # This code is contributed by Shubham Singh |
C#
/* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ using System; public class GFG { static int maxIndexDiff( int [] arr, int n) { int []rightMax = new int [n]; rightMax[n - 1] = arr[n - 1]; int i = 0, j = 0; for (i = n - 2; i >= 0; i--) rightMax[i] = Math.Max(rightMax[i+1] , arr[i]); // rightMax[i] = max{ arr[i...(n-1] } int maxDist = Int32.MinValue; i = 0; while (i < n && j < n) { if (rightMax[j] >= arr[i]) { maxDist = Math.Max( maxDist, j - i); j++; } else // if(rightMax[j] < leftMin[i]) i++; } return maxDist; } // Driver Code public static void Main() { int [] arr = {34, 8, 10, 3, 2, 80, 30, 33, 1}; int n = arr.Length; int maxDiff = maxIndexDiff(arr, n); Console.Write(maxDiff); } } // This code is contributed by Shubham Singh |
Javascript
<script> /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ function maxIndexDiff(arr, n) { var rightMax = new Array(n).fill(0);; rightMax[n - 1] = arr[n - 1]; for ( var i = n - 2; i >= 0; i--){ rightMax[i] = Math.max(rightMax[i+1] , arr[i]); } // rightMax[i] = max{ arr[i...(n-1] } var maxDist = Number.MIN_VALUE; var i = 0; var j = 0; while (i < n && j < n) { if (rightMax[j] >= arr[i]) { maxDist = Math.max( maxDist, j-i ); j++; } else // if(rightMax[j] < leftMin[i]) { i++; } } return maxDist; } // Driver Code var arr = [ 34,8,10,3,2,80,30,33,1]; var n = arr.length; var maxDiff = maxIndexDiff(arr, n); document.write(maxDiff); // This code is contributed by Shubham Singh </script> |
输出
6
时间复杂度：O（n）：由于i和j指针最多遍历n个元素，时间复杂度=O（n）+O（n）=O（n）
空间复杂性：O（n）
使用leftMin[]：
我们也可以只使用leftMin[]数组来实现这一点，其中leftMin[i]=子数组arr[0…i]的min元素
C++
#include <bits/stdc++.h> using namespace std; /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ int maxIndexDiff( int arr[], int n) { int leftMin[n] ; leftMin[0] = arr[0]; for ( int i = 1 ; i<n; i++) leftMin[i] = min(leftMin[i-1], arr[i]); //leftMin[i] = min{ arr[0...i] } int maxDist = INT_MIN; int i = n-1, j = n-1; while (i>=0 && j>=0) { if (arr[j] >= leftMin[i]) { maxDist = max(maxDist, j-i); i--; } else j--; } return maxDist; } // Driver Code int main() { int arr[] = { 34,8,10,3,2,80,30,33,1}; int n = sizeof (arr) / sizeof (arr[0]); int maxDiff = maxIndexDiff(arr, n); cout << maxDiff; return 0; } // This code is contributed by Sourashis Mondal |
JAVA
import java.util.*; class GFG { /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ static int maxIndexDiff( int arr[], int n) { int []leftMin = new int [n]; leftMin[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < n; i++) leftMin[i] = Math.min(leftMin[i - 1 ] , arr[i]); // leftMin[i] = min{ arr[i...(n-1] } int maxDist = Integer.MIN_VALUE; int i = n - 1 , j = n - 1 ; while (i >= 0 && j >= 0 ) { if (arr[j] >= leftMin[i]) { maxDist = Math.max( maxDist, j - i ); i--; } else j--; } return maxDist; } // Driver Code public static void main(String[] args) { int arr[] = { 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 }; int n = arr.length; int maxDiff = maxIndexDiff(arr, n); System.out.print(maxDiff); } } // This code is contributed by Shubham Singh |
Python3
# For a given array arr[], # returns the maximum j – i such that # arr[j] > arr[i] */ def maxIndexDiff(arr, n): leftMin = [ 0 ] * n leftMin[ 0 ] = arr[ 0 ] for i in range ( 1 ,n): leftMin[i] = min (leftMin[i - 1 ], arr[i]) # leftMin[i] = min arr[0...i] maxDist = - 2 * * 32 i = n - 1 j = n - 1 while (i> = 0 and j> = 0 ): if (arr[j] > = leftMin[i]): maxDist = max (maxDist, j - i) i - = 1 else : j - = 1 return maxDist # Driver Code arr = [ 34 , 8 , 10 , 3 , 2 , 80 , 30 , 33 , 1 ] n = len (arr) maxDiff = maxIndexDiff(arr, n) print (maxDiff) # This code is contributed by Shubham Singh |
C#
using System; public class GFG{ /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ static int maxIndexDiff( int [] arr, int n) { int []leftMin = new int [n]; leftMin[0] = arr[0]; int i,j; for ( i = 1; i < n; i++) leftMin[i] = Math.Min(leftMin[i - 1] , arr[i]); // leftMin[i] = min{ arr[i...(n-1] } int maxDist = Int32.MinValue; i = n - 1; j = n - 1; while (i >= 0 && j >= 0) { if (arr[j] >= leftMin[i]) { maxDist = Math.Max( maxDist, j - i ); i--; } else j--; } return maxDist; } // Driver Code static public void Main () { int [] arr = {34, 8, 10, 3, 2, 80, 30, 33, 1}; int n = arr.Length; int maxDiff = maxIndexDiff(arr, n); Console.Write(maxDiff); } } // This code is contributed by Shubham Singh |
Javascript
<script> /* For a given array arr[], returns the maximum j – i such that arr[j] > arr[i] */ function maxIndexDiff(arr, n) { var leftMin = new Array(n).fill(0);; leftMin[0] = arr[0]; for ( var i = 1; i < n; i++){ leftMin[i] = Math.min(leftMin[i-1] , arr[i]); } // leftMin[i] = min{ arr[i...(n-1] } var maxDist = Number.MIN_VALUE; var i = n-1; var j = n-1; while (i >= 0 && j >= 0) { if (arr[j] >= leftMin[i]) { maxDist = Math.max( maxDist, j-i ); i--; } else // if(rightMax[j] < leftMin[i]) { j--; } } return maxDist; } // Driver Code var arr = [ 34,8,10,3,2,80,30,33,1]; var n = arr.length; var maxDiff = maxIndexDiff(arr, n); document.write(maxDiff); // This code is contributed by Shubham Singh </script> |
输出
6
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
