【解题报告】【lintcode362】Sliding Window Maximum

题意

给出一组数字,一个滑动窗口的大小,窗口从开始滑动到数字结束,返回每次窗口中的最大值

解答

由于时间复杂度的要求,我们不能暴力求解,因为这样的复杂度是n*n级别,而题目要求n级别

我们可以通过记录数组下标来解答这个题目

每次新的数字进入时,把小于它的数字下标全部移除,形成递减的结果数组,每次取这个数组的第一个就是当前窗口最大的数了

由于每一个数字只会被操作两次,一次是进入,一次是弹出,所以时间复杂度是O(n)的

代码

u3coding
A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.