生成窗口最大值数组

[编程题]生成窗口最大值数组

热度指数：7214 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置，求每一种窗口状态下的最大值。（如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值）

输入描述:

第一行输入n和w，分别代表数组长度和窗口大小
第二行输入n个整数，表示数组中的各个元素

输出描述:

输出一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值

示例1

输入

8 3
4 3 5 4 3 3 6 7

输出

5 5 5 4 6 7

说明

例如，数组为[4，3，5，4，3，3，6，7]，窗口大小为3时：

[4 3 5] 4 3 3 6 7        窗口中最大值为5

4 [3 5 4] 3 3 6 7        窗口中最大值为5

4 3 [5 4 3] 3 6 7        窗口中最大值为5

4 3 5 [4 3 3] 6 7        窗口中最大值为4

4 3 5 4 [3 3 6] 7        窗口中最大值为6

4 3 5 4 3 [3 6 7]        窗口中最大值为7

输出的结果为{5 5 5 4 6 7}

备注:

算法知识视频讲解

Python

汤普森30

# 利用python中List 模拟 双端队列
N, w = list(map(int, input().split()))
nums = list(map(int, input().split()))

queue = []
res = []
for i in range(N):
    while len(queue)>0 and nums[i] > nums[queue[-1]]:
        queue.pop()
    queue.append(i)
    if queue[0] == i - w:
        queue.pop(0)
    if i >= w-1 and len(queue) > 0:
        res.append(nums[queue[0]])
result = ''
for i in range(len(res)-1):
    result += str(res[i])
    result += ' '
result += str(res[-1])
print(result)

发表于 2019-08-24 11:29:32 回复(0)