如果元素大于或等于其四个相邻元素（左、右、上和下），则该元素为峰值元素。例如，A[i][j]的邻居是A[i-1][j]、A[i+1][j]、A[i][j-1]和A[i][j+1]。对于角元素，缺少的邻域被认为是负无穷大值。 例如：
null
Input : 10 20 15 21 30 14 7 16 32 Output : 3030 is a peak element because all its neighbors are smaller or equal to it. 32 can also be picked as a peak.Input : 10 7 11 17Output : 17
以下是关于这个问题的一些事实： 1：对角线邻接不被视为邻接。 2：峰值元素不一定是最大元素。 3：可以存在多个这样的元素。 4：总是有一个峰值元素。通过用笔和纸创建一些矩阵，我们可以看到这个特性。 方法1：（暴力） 遍历矩阵的所有元素，并检查它是否大于/等于其所有邻居。如果是，则返回元素。 时间复杂度：O（行*列） 辅助空间：O（1） 方法2：（高效） 这个问题主要是 在1D数组中查找峰值元素 .我们在此应用类似的基于二进制搜索的解决方案。
- 考虑中间柱并在其中找到最大元素。
- 让中间列的索引为“mid”，中间列中最大元素的值为“max”，最大元素位于“mat[max_index][mid]”。
- 如果max>=A[index][mid-1]&max>=A[index][pick+1]，max是峰值，则返回max。
- 如果max
- 如果max
- 如果max
下面是上述算法的实现：
C++
// Finding peak element in a 2D Array. #include <bits/stdc++.h> using namespace std; const int MAX = 100; // Function to find the maximum in column 'mid' // 'rows' is number of rows. int findMax( int arr[][MAX], int rows, int mid, int & max) { int max_index = 0; for ( int i = 0; i < rows; i++) { if (max < arr[i][mid]) { // Saving global maximum and its index // to check its neighbours max = arr[i][mid]; max_index = i; } } return max_index; } // Function to find a peak element int findPeakRec( int arr[][MAX], int rows, int columns, int mid) { // Evaluating maximum of mid column. Note max is // passed by reference. int max = 0; int max_index = findMax(arr, rows, mid, max); // If we are on the first or last column, // max is a peak if (mid == 0 || mid == columns - 1) return max; // If mid column maximum is also peak if (max >= arr[max_index][mid - 1] && max >= arr[max_index][mid + 1]) return max; // If max is less than its left if (max < arr[max_index][mid - 1]) return findPeakRec(arr, rows, columns, mid - ceil (( double )mid / 2)); // If max is less than its left // if (max < arr[max_index][mid+1]) return findPeakRec(arr, rows, columns, mid + ceil (( double )mid / 2)); } // A wrapper over findPeakRec() int findPeak( int arr[][MAX], int rows, int columns) { return findPeakRec(arr, rows, columns, columns / 2); } // Driver Code int main() { int arr[][MAX] = { { 10, 8, 10, 10 }, { 14, 13, 12, 11 }, { 15, 9, 11, 21 }, { 16, 17, 19, 20 } }; // Number of Columns int rows = 4, columns = 4; cout << findPeak(arr, rows, columns); return 0; } |
JAVA
// Finding peak element in a 2D Array. class GFG { static int MAX = 100 ; // Function to find the maximum in column // 'mid', 'rows' is number of rows. static int findMax( int [][] arr, int rows, int mid, int max) { int max_index = 0 ; for ( int i = 0 ; i < rows; i++) { if (max < arr[i][mid]) { // Saving global maximum and its index // to check its neighbours max = arr[i][mid]; max_index = i; } } return max_index; } // Function to change the value of [max] static int Max( int [][] arr, int rows, int mid, int max) { for ( int i = 0 ; i < rows; i++) { if (max < arr[i][mid]) { // Saving global maximum and its index // to check its neighbours max = arr[i][mid]; } } return max; } // Function to find a peak element static int findPeakRec( int [][] arr, int rows, int columns, int mid) { // Evaluating maximum of mid column. // Note max is passed by reference. int max = 0 ; int max_index = findMax(arr, rows, mid, max); max = Max(arr, rows, mid, max); // If we are on the first or last column, // max is a peak if (mid == 0 || mid == columns - 1 ) return max; // If mid column maximum is also peak if (max >= arr[max_index][mid - 1 ] && max >= arr[max_index][mid + 1 ]) return max; // If max is less than its left if (max < arr[max_index][mid - 1 ]) return findPeakRec(arr, rows, columns, ( int )(mid - Math.ceil(( double ) mid / 2 ))); // If max is less than its left // if (max < arr[max_index][mid+1]) return findPeakRec(arr, rows, columns, ( int )(mid + Math.ceil(( double ) mid / 2 ))); } // A wrapper over findPeakRec() static int findPeak( int [][] arr, int rows, int columns) { return findPeakRec(arr, rows, columns, columns / 2 ); } // Driver Code public static void main(String[] args) { int [][] arr = {{ 10 , 8 , 10 , 10 }, { 14 , 13 , 12 , 11 }, { 15 , 9 , 11 , 21 }, { 16 , 17 , 19 , 20 }}; // Number of Columns int rows = 4 , columns = 4 ; System.out.println(findPeak(arr, rows, columns)); } } // This code is contributed by // sanjeev2552 |
Python3
# Finding peak element in a 2D Array. MAX = 100 from math import ceil # Function to find the maximum in column 'mid' # 'rows' is number of rows. def findMax(arr, rows, mid, max ): max_index = 0 for i in range (rows): if ( max < arr[i][mid]): # Saving global maximum and its index # to check its neighbours max = arr[i][mid] max_index = i #print(max_index) return max ,max_index # Function to find a peak element def findPeakRec(arr, rows, columns,mid): # Evaluating maximum of mid column. # Note max is passed by reference. max = 0 max , max_index = findMax(arr, rows, mid, max ) # If we are on the first or last column, # max is a peak if (mid = = 0 or mid = = columns - 1 ): return max # If mid column maximum is also peak if ( max > = arr[max_index][mid - 1 ] and max > = arr[max_index][mid + 1 ]): return max # If max is less than its left if ( max < arr[max_index][mid - 1 ]): return findPeakRec(arr, rows, columns, mid - ceil(mid / 2.0 )) # If max is less than its left # if (max < arr[max_index][mid+1]) return findPeakRec(arr, rows, columns, mid + ceil(mid / 2.0 )) # A wrapper over findPeakRec() def findPeak(arr, rows, columns): return findPeakRec(arr, rows, columns, columns / / 2 ) # Driver Code arr = [ [ 10 , 8 , 10 , 10 ], [ 14 , 13 , 12 , 11 ], [ 15 , 9 , 11 , 21 ], [ 16 , 17 , 19 , 20 ] ] # Number of Columns rows = 4 columns = 4 print (findPeak(arr, rows, columns)) # This code is contributed by Mohit Kumar |
C#
// Finding peak element in a 2D Array. using System; class GFG { // Function to find the maximum in column // 'mid', 'rows' is number of rows. static int findMax( int [,] arr, int rows, int mid, int max) { int max_index = 0; for ( int i = 0; i < rows; i++) { if (max < arr[i,mid]) { // Saving global maximum and its // index to check its neighbours max = arr[i,mid]; max_index = i; } } return max_index; } // Function to change the value of [max] static int Max( int [,] arr, int rows, int mid, int max) { for ( int i = 0; i < rows; i++) { if (max < arr[i, mid]) { // Saving global maximum and its // index to check its neighbours max = arr[i, mid]; } } return max; } // Function to find a peak element static int findPeakRec( int [,] arr, int rows, int columns, int mid) { // Evaluating maximum of mid column. // Note max is passed by reference. int max = 0; int max_index = findMax(arr, rows, mid, max); max = Max(arr, rows, mid, max); // If we are on the first or last column, // max is a peak if (mid == 0 || mid == columns - 1) return max; // If mid column maximum is also peak if (max >= arr[max_index, mid - 1] && max >= arr[max_index, mid + 1]) return max; // If max is less than its left if (max < arr[max_index,mid - 1]) return findPeakRec(arr, rows, columns, ( int )(mid - Math.Ceiling(( double ) mid / 2))); // If max is less than its left // if (max < arr[max_index][mid+1]) return findPeakRec(arr, rows, columns, ( int )(mid + Math.Ceiling(( double ) mid / 2))); } // A wrapper over findPeakRec() static int findPeak( int [,] arr, int rows, int columns) { return findPeakRec(arr, rows, columns, columns / 2); } // Driver Code static public void Main () { int [,] arr = {{ 10, 8, 10, 10 }, { 14, 13, 12, 11 }, { 15, 9, 11, 21 }, { 16, 17, 19, 20 }}; // Number of Columns int rows = 4, columns = 4; Console.Write(findPeak(arr, rows, columns)); } } // This code is contributed by ajit. |
Javascript
<script> // Finding peak element in a 2D Array. let MAX = 100; // Function to find the maximum in column // 'mid', 'rows' is number of rows. function findMax(arr, rows, mid, max) { let max_index = 0; for (let i = 0; i < rows; i++) { if (max < arr[i][mid]) { // Saving global maximum and its index // to check its neighbours max = arr[i][mid]; max_index = i; } } return max_index; } // Function to change the value of [max] function Max(arr, rows, mid, max) { for (let i = 0; i < rows; i++) { if (max < arr[i][mid]) { // Saving global maximum and its index // to check its neighbours max = arr[i][mid]; } } return max; } // Function to find a peak element function findPeakRec(arr, rows, columns, mid) { // Evaluating maximum of mid column. // Note max is passed by reference. let max = 0; let max_index = findMax(arr, rows, mid, max); max = Max(arr, rows, mid, max); // If we are on the first or last column, // max is a peak if (mid == 0 || mid == columns - 1) return max; // If mid column maximum is also peak if (max >= arr[max_index][mid - 1] && max >= arr[max_index][mid + 1]) return max; // If max is less than its left if (max < arr[max_index][mid - 1]) return findPeakRec(arr, rows, columns, (mid - Math.ceil(mid / 2))); // If max is less than its left // if (max < arr[max_index][mid+1]) return findPeakRec(arr, rows, columns, (mid + Math.ceil(mid / 2))); } // A wrapper over findPeakRec() function findPeak(arr, rows, columns) { return findPeakRec(arr, rows, columns, parseInt(columns / 2, 10)); } let arr = [[ 10, 8, 10, 10 ], [ 14, 13, 12, 11 ], [ 15, 9, 11, 21 ], [ 16, 17, 19, 20 ]]; // Number of Columns let rows = 4, columns = 4; document.write(findPeak(arr, rows, columns)); </script> |
输出：
21
时间复杂度：O（行*日志（列））。我们重复出现的列数只有原来的一半。在每个递归调用中，我们线性搜索当前中间列中的最大值。 辅助空间：O（列/2）用于递归调用堆栈 资料来源： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf
本文由 罗希特·塔普里亚尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
