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

2021年3月19日12:48:01 发表评论 682 次浏览

## 本文概述

An高效的解决方案可以解决这个问题上)时间使用上)多余的空间。以下是详细的解决方案。

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

## 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#

``````// 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``

## 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#

``````// 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``````

``Index of the element is 4``

O(1)