การหาจุดสูงสุดในอาร์เรย์ 2 มิติ (Peak Element in 2D Array)

องค์ประกอบถือว่าเป็น "จุดสูงสุด" (Peak Element) เมื่อค่าของมันมากกว่าหรือเท่ากับค่าของเพื่อนบ้านทั้งสี่ทิศทาง ได้แก่ บน ล่าง ซ้าย และขวา (ไม่รวมทิศมุม) ในเมทริกซ์อาจมีจุดสูงสุดได้มากกว่าหนึ่งจุด และจุดสูงสุดไม่จำเป็นต้องเป็นค่าสูงสุดของเมทริกซ์ทั้งหมด

การรับค่าและแสดงผล

Input: เมทริกซ์ตัวเลข
10  8  10  10
14 13  12  11
15  9  11  21
16 17  19  20

Output: จุดสูงสุดของเมทริกซ์คือ 21

อัลกอริทึม

findMaxMid(rows, mid, max)

Input: จำนวนแถว คอลัมน์กลาง ตัวแปรสำหรับเก็บค่าสูงสุด

Output: อัปเดตค่าสูงสุดและดัชนีของค่าสูงสุดในคอลัมน์กลาง

Begin
  maxIndex := 0
  for ทุกแถว r ในเมทริกซ์ do
    if max < matrix[r, mid] then
      max = matrix[r, mid]
      maxIndex := r
    end if
  done
  return maxIndex
End

findPeakElement(rows, columns, mid)

Input: จำนวนแถว คอลัมน์ และตำแหน่งคอลัมน์กลาง

Output: จุดสูงสุดในเมทริกซ์

Begin
  maxMid := 0
  maxMidIndex := findMaxMid(rows, mid, maxMid)
  
  if mid เป็นคอลัมน์แรกหรือคอลัมน์สุดท้าย then
    return maxMid
  
  if maxMid >= ค่าด้านซ้ายและขวาในแถวเดียวกัน then
    return maxMid
  
  if maxMid น้อยกว่าค่าด้านซ้าย then
    return findPeakElement(rows, columns, mid - mid/2)
  
  if maxMid น้อยกว่าค่าด้านขวา then
    return findPeakElement(rows, columns, mid + mid/2)
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#define M 4
#define N 4
using namespace std;

int arr[M][N] = {
  {10, 8, 10, 10},
  {14, 13, 12, 11},
  {15, 9, 11, 21},
  {16, 17, 19, 20}
};

int findMaxMid(int rows, int mid, int &max) {
  int maxIndex = 0;
  for (int i = 0; i < rows; i++) {
    if (max < arr[i][mid]) {
      max = arr[i][mid];
      maxIndex = i;
    }
  }
  return maxIndex;
}

int findPeakElement(int rows, int columns, int mid) {
  int maxMid = 0;
  int maxMidIndex = findMaxMid(rows, mid, maxMid);
  
  if (mid == 0 || mid == columns - 1)
    return maxMid;
  
  if (maxMid >= arr[maxMidIndex][mid-1] && maxMid >= arr[maxMidIndex][mid+1])
    return maxMid;
  
  if (maxMid < arr[maxMidIndex][mid-1])
    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