面试题65：滑动窗口的最大值
给定一个数组和滑动窗口的大小，请找出所有滑动窗口中的最大值。例如，如果输入数组是{2,3,4,2,6,2,5,1}以及窗口大小3，那么一共有6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}
leetcode链接 https://leetcode-cn.com/problems/sliding-window-maximum/
解题思路：
思路1：用滑动窗口可以看做是一个队列。当当前窗口滑动时，处于窗口的第一个元素被删除，同时在窗口的末尾添加一个新元素。这个符合队列先进先出的原则。如果能从队列中找到最大值，这个问题就解决了。
在面试题21中，我们实现了一个可以用o(1)时间获得最小值的栈。在面试题7中，我们实现了用两个栈实现一个队列。综上，可以用两个栈实现队列，并通过o1时间获得队列最大值，因此总体复杂度降低为on。
思路2：我们不把滑动窗口中每个值都存入队列，只把有可能成为滑动窗口最大值的值存在队列中。
在存入下一个数字小标之前，判断队列中已有数字是否小于待存入数字。如果已有数字小于待存入数字，这些数字已经不可能是滑动窗口最大值，因此他们将依次从队列尾部删除。将新数据存入。
网友评论