【题目描述】
Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.
给出一个可能包含重复的整数数组，和一个大小为k的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。
【题目链接】
www.lintcode.com/en/problem/sliding-window-maximum/
【题目解析】
遍历数组nums，使用双端队列deque维护滑动窗口内有可能成为最大值元素的数组下标。由于数组中的每一个元素至多只会入队、出队一次，因此均摊时间复杂度为O(n)。记当前下标为i，则滑动窗口的有效下标范围为[i - (k - 1), i]。若deque中的元素下标＜ i - (k - 1)，则将其从队头弹出，deque中的元素按照下标递增顺序从队尾入队。这样就确保deque中的数组下标范围为[i - (k - 1), i]，满足滑动窗口的要求。
当下标i从队尾入队时，顺次弹出队列尾部不大于nums[i]的数组下标（这些被弹出的元素由于新元素的加入而变得没有意义）。deque的队头元素即为当前滑动窗口的最大值
【参考答案】
网友评论