二维阵列中的峰元素

当一项大于或等于该元素的所有四个邻居时，该项目被称为峰值元素。相邻元素是顶部，底部，左侧和右侧元素。对于此问题，我们将考虑一些界限。不将对角线元素检查为相邻元素。矩阵中可以存在一个以上的峰值元素，并且峰值元素不一定是矩阵中最大的元素。

输入输出

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
End

findPeakElement（行，列，中间）

输入-矩阵的行和列，以及中间的行位置。

输出-矩阵中的峰值元素。

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