[mitbbs面经][Google] k largest elements

mitbbs google 最新算法题讲解，sliding window 中查找top K元素。

发题人id：zerocoolcode

发题时间： 3/25/2015

出题公司：google

原帖链接：http://www.mitbbs.com/article_t/JobHunting/32918239.html

题目引用：

Find k-largestelements in a sliding window

A long array A[]with size n is given to you. There is a sliding window of size w which is moving from the very left of thearray to the very right. You can only see the wnumbers in the window. Each time the sliding window moves rightwards by oneposition. Find top k elements in thesliding window when it moves to each n positions.

包子解答：

正如发帖人所述，这道题目是Sliding Window Maximum的变种。如果只是要求最大的元素，那么可以通过原题讲解中的堆栈解法以O(n) 的复杂度解决。当要求输出所有sliding window 的top k 大的元素时，通过直觉，我们可以知道总共有 k*n次输出，所以最少 O(k*n)的时间复杂度是逃不掉的。在这里，包子以多种思路来讲解此题，希望大家能有所收获。

(点击左下角原文链接查看全文)