# -*- coding: utf-8 -*-
'''
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
'''

def maxInWin(numList, winSize):
    if winSize < 1 or winSize > len(numList):
        return []
    if winSize == len(numList):
        return [max(numList)]
    if winSize == 1:
        return numList
    que = [[0,numList[0]]]
    result = []
    for i in range(1,len(numList)):
        x = numList[i]
        if x > que[0][1]:
            que = [[i,x]]
        else:
            while que[-1][1] <= x:
                que.pop()
            que.append([i,x])
        if i >= winSize-1:
            result.append(que[0][1])
        if que[0][0] <= i-winSize+1:
            que.pop(0)
    return result

'''
思路：用一个双头队列暂存可能的最大值及其下标。每当读入一个数字k，从队尾到队头依次对比，将小于等于k的数字都弹出队列，并将k值以及k的下标值存入队尾。此时位于队头的数字便是该窗口的最大值。若队头的数字已经是窗口最左边的数字，则需弹出队列，然后再将窗口向前滑一格。
注意：牛客上将窗口长度大于数组长度的情况认为应该返回空数组
边界：空数组，窗口为1，窗口大于1，窗口长度大于等于数组长度。递增数组，递减数组，乱序数组
'''
# 测试用例
print('输入：%s %s，输出：%s，答案：%s' % ([], 2, maxInWin([], 2), []))
print('输入：%s %s，输出：%s，答案：%s' % ([1], 0, maxInWin([1], 0), []))
print('输入：%s %s，输出：%s，答案：%s' % ([1,2], 1, maxInWin([1,2], 1), [1,2]))
print('输入：%s %s，输出：%s，答案：%s' % ([1,2], 2, maxInWin([1,2], 2), [2]))
print('输入：%s %s，输出：%s，答案：%s' % ([1,2], 3, maxInWin([1,2], 3), []))
print('输入：%s %s，输出：%s，答案：%s' % ([1,2,3,4,5,6], 3, maxInWin([1,2,3,4,5,6], 3), [3,4,5,6]))
print('输入：%s %s，输出：%s，答案：%s' % ([7,6,5,4,3,2], 3, maxInWin([7,6,5,4,3,2], 3), [7,6,5,4]))
print('输入：%s %s，输出：%s，答案：%s' % ([7,1,2,6,3,1,4], 3, maxInWin([7,1,2,6,3,1,4], 3), [7,6,6,6,4]))
