leetcode239 -- Sliding Window Maximum（就是maxpooling一维的那个)

# 小郑之家~

### 题目


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. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

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

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



class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""

ret = []
if len(nums)<k or k==0:
return []
queue = []
data = nums
for i in range(k):
while len(queue)>0 and data[i]>=data[queue[-1]]:
del(queue[-1])

queue.append(i)
for i in range(k, len(data)):

ret.append(data[queue[0]])

while len(queue)>0 and data[i]>= data[queue[-1]]:
del(queue[-1])
queue.append(i)

if len(queue)>0 and i-queue[0]>=k:
del(queue[0])

ret.append(data[queue[0]])

return ret


def mapooling(data,k):
ret = []

if len(data) ==0 or k<=0 or len(data)<k:
return ret

queue = []

for i in range(len(data)):
if len(queue)>0:
# 先决定什么时候出队
if i-queue[0] >=k:   # 这时候指的是如果窗口的长度已经大于k了，说明这时候首元素已经没有用了.
del(queue[0])

while len(queue)>0 and data[i] >= data[queue[-1]]:   # 因为这时候队列的最后一个元素不是最大值
del(queue[-1])

queue.append(i)

if i+1>=k:   # 如果当前遍历的长度已经过了窗口的长度了就可以存结果了.
ret.append(data[queue[0]])

return ret