二维阵列中的峰元素
当一项大于或等于该元素的所有四个邻居时，该项目被称为峰值元素。相邻元素是顶部，底部，左侧和右侧元素。对于此问题，我们将考虑一些界限。不将对角线元素检查为相邻元素。矩阵中可以存在一个以上的峰值元素，并且峰值元素不一定是矩阵中最大的元素。
输入输出
Input: A matrix of different numbers. 10 8 10 10 14 13 12 11 15 9 11 11 15 9 11 21 16 17 19 20 Output: The peak element of the matrix. Here the peak element is: 21
算法
findMaxMid（行，中间，最大值）
输入： 矩阵的行数，中间行，最大元素作为输出参数。
输出： 更新max元素的max项目和索引。
Begin
maxIndex := 0
for all rows r in the matrix, do
if max < matrix[i, mid], then
max = matrix[i, mid],
maxIndex := r
done
return maxIndex
EndfindPeakElement（行，列，中间）
输入-矩阵的行和列，以及中间的行位置。
输出-矩阵中的峰值元素。
Begin
maxMid := 0
maxMidIndex := findMaxMid(rows, mid, maxMid)
if mid is first or last column, then
return maxMid
if maxMid>= item of previous and next row for mid column, then
return maxMid
if maxMid is less than its left element, then
res := findPeakElement(rows, columns, mid – mid/2)
return res
if maxMid is less than its right element, then
res := findPeakElement(rows, columns, mid + mid/2)
return res
End示例
#include<iostream>
#define M 4
#define N 4
using namespace std;
intarr[M][N] = {
{10, 8, 10, 10},
{14, 13, 12, 11},
{15, 9, 11, 21},
{16, 17, 19, 20}
};
intfindMaxMid(int rows, int mid, int&max) {
intmaxIndex = 0;
for (int i = 0; i < rows; i++) { //find max element in the mid column
if (max <arr[i][mid]) {
max = arr[i][mid];
maxIndex = i;
}
}
return maxIndex;
}
intfindPeakElement(int rows, int columns, int mid) {
intmaxMid = 0;
intmaxMidIndex = findMaxMid(rows, mid, maxMid);
if (mid == 0 || mid == columns-1) //for first and last column, the maxMid is maximum
return maxMid;
//如果maxMid也是峰值
if (maxMid>= arr[maxMidIndex][mid-1] &&maxMid>= arr[maxMidIndex][mid+1])
return maxMid;
if (maxMid<arr[maxMidIndex][mid-1]) // If maxMid is less than its left element
return findPeakElement(rows, columns, mid - mid/2);
return findPeakElement(rows, columns, mid+mid/2);
}
int main() {
int row = 4, col = 4;
cout<< "The peak element is: "<<findPeakElement(row, col, col/2);
}输出结果
The peak element is: 21