作者介绍：本文作者水蜜桃同学，硕士毕业于上海交大，前ACM炮灰选手，现就职于腾讯。
本期面试题解，作者从历年的面试题和考题中总结整理了部分高频的题目，并由此给出了答题思路和要点，希望在接下来的秋招求职中能够多练练题，掌握好答题思路。
这是笔者水蜜桃同学去年在上海面试某D轮互联网独角兽企业面试时遇到的一道算法题，题面很简单：记一个矩阵所有元素中的最大值为这个矩阵的C值。给出一个n*n的矩阵M，求所有k*k(kn)的子矩阵的C值之和。例如下面这个5*5的矩阵，若k=3，那么图中绿色矩形框圈出的3*3子矩阵的C值为9，蓝色矩形框圈出的3*3子矩阵的C值则为6，它的9个3*3的子矩阵的C值分别为9,9,8,7,7,6,6,6,6，其C值之和为64。
看到这个题目，最朴素的方法很简单，当然就是枚举出所有的k*k的子矩阵，逐一遍历出每个k*k子矩阵中的最大值，再把它们加起来就OK了。如果你给出的是这个答案，那么你就和机智的水蜜桃同学一样，给出了一个非常正确的解法。相信每个有编程基础的同学完成这段编码逻辑不会有任何问题的,不过这个算法的复杂度高达O((n-k+1)^2*k^2)。
虽然我们朴素的解法确实挺暴力的，但也能给我们一些启发吧。我们稍微观察一下就可以发现，如果我们横向地看相邻的两个k*k的子矩阵，中间的k-1列的数据是完全一样的。例如在计算Matrix1和Matrix2的C值时，蓝色部分的数据时完全一样的，我们完全没必要在枚举这两个k*k子矩阵的子矩阵时，把这部蓝色分数据计算两次。认识到了这一点，笔者相信机智的同学们已经可以把这道题的复杂度降下来一点了，现在应该是O((2n-k+1)*k*n)。
不过这个优化过的解法依旧挺暴力的，细心的同学们还是会发现有好多做了重复计算的地方。其实，在遇到复杂问题的时候，将问题简化往往能给我们带来新的思路。
我们不妨先把这个问题中二维的矩阵简化成一维的数列。那么现在的问题就变成了一个求连续的滑动窗口最值问题：给出一个长度为n的数列和一个长度为k(kn)的窗口，记录滑动窗口位于每个位置下的下的最大值，求这些最大值和。
如果我们维护一个长度为k的队列，使得队首即为窗口中的最大值，那么当窗口滑动时，每次只要输出（求和的话就是累加）队首的值就可以解决问题了。但这个队列要怎么实现呢？既然要保证队列中的队首就是窗口中的最大值，那我们就必须保证每次向后滑动窗口时，处在新位置窗口中的最大值依旧在队首。那如果队列中存储的最大值不在窗口范围内，需要该弹出了怎么办呢？我们只需要记录下每个元素的位置，判断是否在区间内即可。一旦队首因超出滑窗的范围被弹出，原本队列中的第二个元素就变成了队首，我们就要保证这个数现在是窗口内最大的数，如果它不是，那说明进入滑窗范围内的新元素应该成为队首。那么是不是说，我们需要将这个长度为k的窗口中的每一个数都存起来呢？不是的，并不是每个数被记录都有意义的。举个例子，ai和aj两个数，ij，如果aiaj，那么两个数都应该记录；但是如果ai≤aj，那么当aj进入区间后，ai的记录就没有意义了。很好理解，我们假设每个数作为窗口中最大值的次数为它的贡献，当aj进入区间以后，在区间中存在的时间一定比ai长，也就说明ai一定不会再做贡献了，对于我们能够确定的没有贡献的元素，便可以直接删去，以维护单调队列的单调性。其实这个数据结构就是单调队列了，参加过ACM竞赛的同学一定已经很熟悉了。求连续的滑动窗口最大值的就贴在下面了。
现在我们已经了解单调队列了，它能够以的O(n)时间复杂度解决：在一个数列中求滑动窗口位于每个位置下的最值问题。此时如果我们横向地看一个k*n的子矩阵，记第i列的最大值为ai，依次处理k*n子矩阵中的每一列得到一个长度为n的数列a，然后用单调队列处理出数列a下长度为k的滑动窗口在每个位置下的最大值，这些最大值就相当于两两相邻的k*k的子矩阵的中的最大值了。至此，我们的时间复杂度已经降到了O((n-k+1)^2*k)。
当然，我们还有更棒的解法。如果我们先用单调队列，把每一列长度为k的滑动窗口的最大值先预处理出来，就像这样，先变成这么一个k*n的矩阵，然后再用一次单调队列，把每一行中长度为k的滑动窗口中的最大值求出来做一下累加，依旧是正解哦，但此时，解决这道题的时间复杂度已经被我们降到了O((n-k+1)*k)，这个复杂度，面试官应该是可以接受了。
回顾一下我们解决这个问题的过程：首先是提出了一个最朴素的解法，虽然时间复杂度很高，但是给了我们优化的思路；接着，我们把复杂的问题简单化，将这一简化后的问题用单调队列解决；最后我们回到原来的问题，将简化问题用到的方法和之前优化的思路结合，就算是比较好的解决了这道题了。
求职礼包
《届互联网名企最新校招信息汇总》《套精选求职简历模板，只为免费送你》求职面经
《校招凉面-今日头条京东算法岗面经》《校招热面-渣渣学长给学弟学妹的求职建议》《职场-互联网上班公司名单-不要》《爆尿-互联网公司福利大比拼》