Phần tử đỉnh (Peak Element) trong mảng 2D

Một phần tử được gọi là phần tử đỉnh (peak element) khi nó lớn hơn hoặc bằng cả bốn phần tử lân cận: trên, dưới, trái và phải. Các phần tử đường chéo không được coi là lân cận. Có thể tồn tại nhiều phần tử đỉnh trong một ma trận, và phần tử đỉnh không nhất thiết phải là phần tử lớn nhất trong ma trận.

Đầu vào và Đầu ra

Đầu vào: Ma trận các số khác nhau.
10  8  10  10
14 13  12  11
15  9  11  21
16 17  19  20
Đầu ra: Phần tử đỉnh của ma trận. Ở đây phần tử đỉnh là: 21

Thuật toán

findMaxMid(rows, mid, max)

Đầu vào: Số hàng của ma trận, cột giữa, một phần tử max làm đối số đầu ra.

Đầu ra: Cập nhật phần tử max và chỉ số của phần tử max.

Bắt đầu
  maxIndex := 0
  với mọi hàng r trong ma trận, thực hiện
    nếu max < matrix[i, mid] thì
      max = matrix[i, mid]
      maxIndex := r
  kết thúc
  trả về maxIndex
Kết thúc

findPeakElement(rows, columns, mid)

Đầu vào: Số hàng và cột của ma trận, và vị trí cột giữa.

Đầu ra: Phần tử đỉnh trong ma trận.

Bắt đầu
  maxMid := 0
  maxMidIndex := findMaxMid(rows, mid, maxMid)
  nếu mid là cột đầu hoặc cột cuối thì
    trả về maxMid
  nếu maxMid >= phần tử hàng trước và hàng sau tại cột mid thì
    trả về maxMid
  nếu maxMid nhỏ hơn phần tử bên trái thì
    res := findPeakElement(rows, columns, mid - mid/2)
    trả về res
  nếu maxMid nhỏ hơn phần tử bên phải thì
    res := findPeakElement(rows, columns, mid + mid/2)
    trả về res
Kết thúc

Ví dụ (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++) {
    // tìm phần tử lớn nhất ở cột giữa
    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) // với cột đầu và cuối, maxMid là lớn nhất
    return maxMid;
  
  // Nếu maxMid cũng là đỉnh
  if (maxMid >= arr[maxMidIndex][mid-1] && maxMid >= arr[maxMidIndex][mid+1])
    return maxMid;
  
  if (maxMid < arr[maxMidIndex][mid-1]) // Nếu maxMid nhỏ hơn phần tử bên trái
    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);
}

Đầu ra

The peak element is: 21