找到一个元素，它前面的所有元素都比它小，后面的所有元素都比它大

本文概述

C ++
Java
Python3
C#
的PHP
C ++
Python3
C#

给定一个数组, 找到一个元素, 在该元素之前所有元素都小于该元素, 之后所有元素都大于该元素。如果存在这样的元素, 则返回该元素的索引, 否则返回-1。
例子：

输入：arr [] = {5, 1, 4, 3, 6, 8, 10, 7, 9}; 输出：4说明：arr [4]左侧的所有元素都小于它, 右侧的所有元素都大于。输入：arr [] = {5, 1, 4, 4}; 输出：-1说明：此类索引不存在。

预期时间复杂度：O(n)。
推荐：请在"
实践
首先, 在继续解决方案之前。
一种简单的解决方案是一个一个地考虑每个元素。对于每个元素, 将其与左侧的所有元素和右侧的所有元素进行比较。该解决方案的时间复杂度为O(n2)。
An高效的解决方案可以解决这个问题上)时间使用上)多余的空间。以下是详细的解决方案。

创建两个数组leftMax []和rightMin []。
从左到右遍历输入数组, 并填充leftMax [], 使leftMax [i]包含输入数组中从0到i-1的最大元素。
从右到左遍历输入数组, 并填充rightMin [], 以使rightMin [i]在输入数组中包含从到n-1到i + 1的最小元素。
遍历输入数组。对于每个元素arr [i], 检查arr [i]是否大于leftMax [i]并小于rightMin [i]。如果是, 请返回i。

进一步优化上面的方法是仅使用一个额外的数组, 并且仅遍历输入数组两次。第一次遍历与上面相同, 并填充leftMax []。下一个遍历从右侧遍历并跟踪最小值。第二次遍历还会找到所需的元素。
【找到一个元素，它前面的所有元素都比它小，后面的所有元素都比它大】下图是上述方法的模拟：

文章图片
下面是上述方法的实现。
C ++

// C++ program to find the element which is greater than // all left elements and smaller than all right elements. #include < bits/stdc++.h> using namespace std; // Function to return the index of the element which is greater than // all left elements and smaller than all right elements. int findElement( int arr[], int n) { // leftMax[i] stores maximum of arr[0..i-1] int leftMax[n]; leftMax[0] = INT_MIN; // Fill leftMax[]1..n-1] for ( int i = 1; i < n; i++) leftMax[i] = max(leftMax[i-1], arr[i-1]); // Initialize minimum from right int rightMin = INT_MAX; // Traverse array from right for ( int i=n-1; i> =0; i--) { // Check if we found a required element if (leftMax[i] < arr[i] & & rightMin > arr[i]) return i; // Update right minimum rightMin = min(rightMin, arr[i]); } // If there was no element matching criteria return -1; } // Driver program int main() { int arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9}; int n = sizeof arr / sizeof arr[0]; cout < < "Index of the element is " < < findElement(arr, n); return 0; }

Java

// Java program to find the element which is greater than // all left elements and smaller than all right elements. import java.io.*; import java.util.*; public class GFG { static int findElement( int [] arr, int n) { // leftMax[i] stores maximum of arr[0..i-1] int [] leftMax = new int [n]; leftMax[ 0 ] = Integer.MIN_VALUE; // Fill leftMax[]1..n-1] for ( int i = 1 ; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1 ], arr[i - 1 ]); // Initialize minimum from right int rightMin = Integer.MAX_VALUE; // Traverse array from right for ( int i = n - 1 ; i > = 0 ; i--) { // Check if we found a required element if (leftMax[i] < arr[i] & & rightMin > arr[i]) return i; // Update right minimum rightMin = Math.min(rightMin, arr[i]); }// If there was no element matching criteria return - 1 ; } // Driver code public static void main(String args[]) { int [] arr = { 5 , 1 , 4 , 3 , 6 , 8 , 10 , 7 , 9 }; int n = arr.length; System.out.println( "Index of the element is " + findElement(arr, n)); } // This code is contributed // by rachana soma }

Python3

# Python3 program to find the element which is greater than # all left elements and smaller than all right elements. def findElement(arr, n):# leftMax[i] stores maximum of arr[0..i-1] leftMax = [ None ] * n leftMax[ 0 ] = float ( '-inf' ) # Fill leftMax[]1..n-1] for i in range ( 1 , n): leftMax[i] = max (leftMax[i - 1 ], arr[i - 1 ]) # Initialize minimum from right rightMin = float ( 'inf' ) # Traverse array from right for i in range (n - 1 , - 1 , - 1 ):# Check if we found a required element if leftMax[i] < arr[i] and rightMin > arr[i]: return i # Update right minimum rightMin = min (rightMin, arr[i])# If there was no element matching criteria return - 1 # Driver program if __name__ = = "__main__" : arr = [ 5 , 1 , 4 , 3 , 6 , 8 , 10 , 7 , 9 ] n = len (arr) print ( "Index of the element is" , findElement(arr, n))# This code is contributed by Rituraj Jain

// C# program to find the element which is greater than // all left elements and smaller than all right elements. using System; class GFG { static int findElement( int [] arr, int n) { // leftMax[i] stores maximum of arr[0..i-1] int [] leftMax = new int [n]; leftMax[0] = int .MinValue; // Fill leftMax[]1..n-1] for ( int i = 1; i < n; i++) leftMax[i] = Math.Max(leftMax[i - 1], arr[i - 1]); // Initialize minimum from right int rightMin = int .MaxValue; // Traverse array from right for ( int i=n-1; i> =0; i--) { // Check if we found a required element if (leftMax[i] < arr[i] & & rightMin > arr[i]) return i; // Update right minimum rightMin = Math.Min(rightMin, arr[i]); } // If there was no element matching criteria return -1; } // Driver program public static void Main() { int [] arr = {5, 1, 4, 3, 6, 8, 10, 7, 9}; int n = arr.Length; Console.Write( "Index of the element is " + findElement(arr, n)); } } // This code is contributed // by Akanksha Rai(Abby_akku)

的PHP

< ?php // PHP program to find the element // which is greater than all left // elements and smaller than all // right elements. function findElement( $arr , $n ) { // leftMax[i] stores maximum // of arr[0..i-1] $leftMax = array (0); $leftMax [0] = PHP_INT_MIN; // Fill leftMax[]1..n-1] for ( $i = 1; $i < $n ; $i ++) $leftMax [ $i ] = max( $leftMax [ $i - 1], $arr [ $i - 1]); // Initialize minimum from right $rightMin = PHP_INT_MAX; // Traverse array from right for ( $i = $n - 1; $i > = 0; $i --) { // Check if we found a required // element if ( $leftMax [ $i ] < $arr [ $i ] & & $rightMin > $arr [ $i ]) return $i ; // Update right minimum $rightMin = min( $rightMin , $arr [ $i ]); } // If there was no element // matching criteria return -1; } // Driver Code $arr = array (5, 1, 4, 3, 6, 8, 10, 7, 9); $n = count ( $arr ); echo "Index of the element is " , findElement( $arr , $n ); // This code is contributed // by Sach_Code ?>

输出如下：

Index of the element is 4

时间复杂度：
上)
辅助空间：
上)
感谢Gaurav Ahirwar提供上述解决方案。
空间优化方法：
C ++

// C++ program to find the element which is greater than // all left elements and smaller than all right elements. #include < bits/stdc++.h> using namespace std; int findElement( int a[], int n) { // Base case if (n == 1 || n == 2) { return -1; } // 1.element is the possible candidate for the solution // of the problem. // 2.idx is the index of the possible // candidate. // 3.maxx is the value which is maximum on the // left side of the array. // 4.bit tell whether the loop is // terminated from the if condition or from the else // condition when loop do not satisfied the condition. // 5.check is the variable which tell whether the // element is updated or not int element = a[0], maxx = a[0], bit = -1, check = 0; int idx = -1; // The extreme two of the array can not be the solution // Therefore iterate the loop from i = 1 to < n-1 for ( int i = 1; i < (n - 1); ) { // here we find the possible candidate where Element // with left side smaller and right side greater. // when the if condition fail we check and update in // else condition. if (a[i] < maxx & & i < (n - 1)) { i++; bit = 0; } // here we update the possible element if the // element is greater than the maxx (maximum element // so far). In while loop we sur-pass the value which // is greater than the element else { if (a[i] > = maxx) { element = a[i]; idx = i; check = 1; maxx = a[i]; } if (check == 1) { i++; } bit = 1; while (a[i] > = element & & i < (n - 1)) { if (a[i] > maxx) { maxx = a[i]; } i++; } check = 0; } } // checking for the last value and whether the loop is // terminated from else or if block. if (element < = a[n - 1] & & bit == 1) { return idx; } else { return -1; } } // Driver Code int main() { int arr[] = { 5, 1, 4, 3, 6, 8, 10, 7, 9 }; int n = sizeof arr / sizeof arr[0]; // Function Call cout < < "Index of the element is " < < findElement(arr, n); return 0; }

Python3

# Python3 program to find the element which # is greater than all left elements and # smaller than all right elements. def findElement (a, n): # Base case if (n = = 1 or n = = 2 ): return - 1 # 1. element is the possible candidate # for the solution of the problem # 2. idx is the index of the # possible candidate # 3. maxx is the value which is maximum # on the left side of the array # 4. bit tell whether the loop is # terminated from the if condition or # from the else condition when loop do # not satisfied the condition. # 5. check is the variable which tell # whether the element is updated or not element, maxx, bit = a[ 0 ], a[ 0 ], - 1 check = 0 idx = - 1 # The extreme of the array can't be # the solution Therefore iterate # the loop from i = 1 to < n-1 i = 1 while (i < (n - 1 )): # Here we find the possible candidate # where element with left side smaller # and right side greater. when the if # condition fail we check and update # in else condition if (a[i] < maxx and i < (n - 1 )): i + = 1 bit = 0 # Here we update the possible element # if the element is greater than the # maxx (maximum element so far). In # while loop we sur-pass the value # which is greater than the element else : if (a[i] > = maxx): element = a[i] idx = i check = 1 maxx = a[i] if (check = = 1 ): i + = 1 bit = 1 while (a[i] > = element and i < (n - 1 )): if (a[i] > maxx): maxx = a[i] i + = 1 check = 0 # Checking for the last value and whether # the loop is terminated from else or # if block if (element < = a[n - 1 ] and bit = = 1 ): return idx else : return - 1 # Driver Code if __name__ = = '__main__' :arr = [ 5 , 1 , 4 , 3 , 6 , 8 , 10 , 7 , 9 ] n = len (arr) # Function call print ( "Index of the element is" , findElement(arr, n)) # This code is contributed by himanshu77

// C# program to find the element // which is greater than all left // elements and smaller than all // right elements. using System; class GFG{static int findElement( int []a, int n) {// Base case if (n == 1 || n == 2) { return -1; }// 1.element is the possible candidate for // the solution of the problem. // 2.idx is the index of the possible // candidate. // 3.maxx is the value which is maximum on the // left side of the array. // 4.bit tell whether the loop is // terminated from the if condition or from // the else condition when loop do not // satisfied the condition. // 5.check is the variable which tell whether the // element is updated or not int element = a[0], maxx = a[0], bit = -1, check = 0; int idx = -1; // The extreme two of the array can // not be the solution. Therefore // iterate the loop from i = 1 to < n-1 for ( int i = 1; i < (n - 1); ) {// Here we find the possible candidate // where Element with left side smaller // and right side greater. When the if // condition fail we check and update in // else condition. if (a[i] < maxx & & i < (n - 1)) { i++; bit = 0; }// Here we update the possible element // if the element is greater than the // maxx (maximum element so far). In // while loop we sur-pass the value which // is greater than the element else { if (a[i] > = maxx) { element = a[i]; idx = i; check = 1; maxx = a[i]; } if (check == 1) { i++; } bit = 1; while (a[i] > = element & & i < (n - 1)) { if (a[i] > maxx) { maxx = a[i]; } i++; } check = 0; } }// Checking for the last value and whether // the loop is terminated from else or // if block. if (element < = a[n - 1] & & bit == 1) { return idx; } else { return -1; } } // Driver code public static void Main( string [] args) { int []arr = { 5, 1, 4, 3, 6, 8, 10, 7, 9 }; int n = arr.Length; // Function Call Console.Write( "Index of the element is " + findElement(arr, n)); } } // This code is contributed by rutvik_56

输出如下