snap 电面 挂

snap电面挂经  投的是machine learning engineer， 面试的人是一个做inference modal的小哥白人。
题目是

给一个matrix ， 算出matrix 里面所有k*k block， 每个block的元素最大值， 并且存在一个矩阵里面，返回矩阵。
有点像matrix block sum这题 ，但是比它简单很多。
给了40分钟写题。

无奈挂了

LZ描述的这一题可比LC上那个mtrix block sum要难啊，毕竟最大值函数没有累加性。为了快速求出结果，最好的还是用单调队列（上面朋友说的二维线段树有点太复杂了，面试官自己肯定都搞不定），不过是二维的。也就是有一个array of deque，其中每一个deque是一个单调队列。每一个行，对所有单调队列进行更新，找出各自column的最大值。然后以这些最大值为基础再用一次单调队列，对这行的从左往右进行求解。

感觉不是很好做啊，二维的线段树？

常规做法应该是遍历每列的和，把二维先压成一维（O(N2)），然后用deque（O(N)）做吧
尔山玖的2D版本
不知道有没有其他什么高级做法