private static int[][] findMax(int[][] array, int k) {
int[][] row = new int[array.length][array[0].length - k + 1];
for (int i = 0; i < array.length; i++) {
row[i] = maxK(array[i], k);
}
int[][] res = new int[array.length - k + 1][row[0].length];
for (int i = 0; i < row[0].length; i++) {
int[] temp = new int[row.length];
for (int t = 0; t < row.length; t++) {
temp[t] = row[t][i];
}
int[] tempR = maxK(temp, k);
for (int t = 0; t < tempR.length; t++) {
res[t][i] = tempR[t];
}
}
return res;
}
private static int[] maxK(int[] array, int k) {
if (array == null || k == 1) {
return array;
}
int[] res = new int[array.length - k + 1];
Deque<Integer> deque = new ArrayDeque();
for (int i = 0; i < array.length; i++) {
while(!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
while (!deque.isEmpty() && array[deque.peekLast()] < array[i]) {
deque.pollLast();
}
deque.offer(i);
if (i - k + 1 >= 0) {
res[i - k + 1] = array[deque.peek()];
}
}
return res;
}
// Refer to https://leetcode.com/problems/sliding-window-maximum/
interface SlidingWindowMax {
void add(int num);
void pop();
int max();
}
int m, n;
int[][] matrix;
int[][] res;
SlidingWindowMax[] cols = new SlidingWindowMax[m];
for (int endRow = 0; endRow < m; endRow++) {
SlidingWindowMax cur = new SlidingWindowMax();
for (int i = 0; i < n; i++) {
cols[i].add(matrix[endRow][i]);
if (endRow >= k - 1) {
// now we may have square
cur.add(cols[i].max());
cols[i].pop();
if (i >= k - 1) {
// found square
res[endRow - k + 1][i - k + 1] = cur.max();
cur.pop();
}
}
}
}
