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

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

本文概述

给定一个数组, 找到一个元素, 在该元素之前所有元素都小于该元素, 之后所有元素都大于该元素。如果存在这样的元素, 则返回该元素的索引, 否则返回-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高效的解决方案可以解决这个问题上)时间使用上)多余的空间。以下是详细的解决方案。

  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。

进一步优化上面的方法是仅使用一个额外的数组, 并且仅遍历输入数组两次。第一次遍历与上面相同, 并填充leftMax []。下一个遍历从右侧遍历并跟踪最小值。第二次遍历还会找到所需的元素。

下图是上述方法的模拟：

找到所有元素都小于它的元素，然后所有元素都大于的元素1

下面是上述方法的实现。

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

时间复杂度：

上)

辅助空间：

上)

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

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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: