Поиск локальных максимумов в двумерном массиве

Локальный максимум в двумерном массиве может быть определен как значение такое, что все его 4 соседа меньше или равны ему, т. е. для того, чтобы a[i][j]был локальным максимумом,

a[i+1][j] <= a[i][j] 
&& a[i-1][j] <= a[i][j]
&& a[i][j+1] <= a[i][j]
&& a[i+1][j-1] <= a[i][j]

меня попросили найти все локальные максимумы в задан двумерный массив.

Наивным способом сделать это было бы просто пройтись по всем элементам и проверить, является ли каждый элемент локальным максимумом. Это будет O( n^2 ). Я чувствую, что вы не можете сделать лучше этого, хотя мой друг настаивает на том, что должен существовать асимптотически лучший алгоритм. Любые подсказки?

Я думал в духе «Разделяй и властвуй», но чувствую, что было бы невозможно обнаружить все локальные максимумы, не перебирая все числа, которые обязательно будут O( n^2 ). Я прав или я что-то упустил?