Python滑动窗口的最大值

本文阅读 3 分钟
首页 Python笔记 正文

我们把可能成为滑动窗口的最大值的数值下标存入一个两端开口的队列index中。首先遍历输入数组,在遍历次数小于窗口长度的时候,如果index数组里面含有元素而且元素后面的下标值对应的输入数组的数如果小于当前遍历到的输入数组元素值,那么就把尾部的元素下标值不断pop出来,再压入当前输入元素对应的下标值。然后再从等于滑动窗口大小的位置继续遍历输入数组。首先把index数组的头元素下标值对应输入数组值压入输出数组。同样的,如果index数组里面含有元素而且元素后面的下标值对应的输入数组的数如果小于当前遍历到的输入数组元素值,那么就把尾部的元素下标值不断pop出来,同时,如果index数组内有元素,而且当一个数字的下标与当前处理的数字的下标只差大于或等于滑动窗口的大小时,这个数字已经从窗口中画出,可以从队列中删除了,再压入当前输入元素对应的下标值。最后还需要在输出数组中append一下index手元素下标对应的输入元素值。

'''
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。
例如,如果输入数组{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]}。
'''

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        if not num or size <= 0:
            return []
        deque = []
        if len(num) >= size:
            index = []
            for i in range(size):
                while len(index) > 0 and num[i] > num[index[-1]]:
                    index.pop()
                index.append(i)

            for i in range(size, len(num)):
                deque.append(num[index[0]])
                while len(index) > 0 and num[i] >= num[index[-1]]:
                    index.pop()
                if len(index) > 0 and index[0] <= i - size:
                    index.pop(0)
                index.append(i)

            deque.append(num[index[0]])
        return deque

test = [2, 3, 4, 2, 6, 2, 5, 1]
s = Solution()
print(s.maxInWindows(test, 3))
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python数据流中的中位数
« 上一篇 01-21
Python矩阵中的路径
下一篇 » 01-21

发表评论