## 题目描述：

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

```Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7```

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:

You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:

Could you solve it in linear time?

Hint:

How about using a data structure such as deque (double-ended queue)?

The queue size need not be the same as the window’s size.

Remove redundant elements and the queue should store only elements that need to be considered.

## 题目大意：

```Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7```

## 解题思路：

```遍历数组nums，使用双端队列deque维护滑动窗口内有可能成为最大值元素的数组下标

deque的队头元素即为当前滑动窗口的最大值```

## Python代码：

``````class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer[]}
def maxSlidingWindow(self, nums, k):
dq = collections.deque()
ans = []
for i in range(len(nums)):
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
if dq[0] == i - k:
dq.popleft()
if i >= k - 1:
ans.append(nums[dq[0]])
return ans
``````

Pingbacks已关闭。

1. 游泳的鱼儿 发布于 2015年7月20日 14:32 #

做友链吗? opdev.cn

2. 在线疯狂 发布于 2015年7月21日 15:12 #

看了下你的站，还比较年轻，站龄比较短，再积累一些原创文章吧，嘿嘿