59 滑动窗口的最大值

CSDN作者独孤呆博
写的很好,贴一下方便自己以后复习。
···class Solution:
def maxInWindows(self, num, size):
# 如果数组 num 不存在,则返回 []
if not num:
return []
# 如果滑动窗口的大小大于数组的大小,或者 size 小于 0,则返回 []
if size > len(num) or size <1:
return []

    # 如果滑动窗口的大小为 1 ,则直接返回原始数组
    if size == 1:
        return num

    # 存放最大值,次大值的数组,和存放输出结果数组的初始化
    temp = [0]
    res = []

    # 对于数组中每一个元素进行判断
    for i in range(len(num)):
        # 判断第 i 个元素是否可以加入 temp 中
        # 如果比当前最大的元素还要大,清空 temp 并把该元素放入数组
        # 首先判断当前最大的元素是否过期
        if i -temp[0] > size-1:
            temp.pop(0)
        # 将第 i 个元素与 temp 中的值比较,将小于 i 的值都弹出
        while (len(temp)>0 and num[i] >= num[temp [-1]]):
            temp.pop()
        # 如果现在 temp 的长度还没有达到最大规模,将元素 i 压入
        if len(temp)< size-1:
            temp.append(i)
        # 只有经过一个完整的窗口才保存当前的最大值
        if i >=size-1:
            res.append(num[temp [0]])
    return res

s = Solution()
A = [2,3,4,2,6,2,5,1]
print(s.maxInWindows(A,3))

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 本系列导航:剑指offer(第二版)java实现导航帖 面试题59:滑动窗口的最大值 题目要求:给定一个数组和滑动...
    ryderchan阅读 3,186评论 0 3
  • Lua 5.1 参考手册 by Roberto Ierusalimschy, Luiz Henrique de F...
    苏黎九歌阅读 13,949评论 0 38
  • “单位搬迁已六年,时光匆匆如昨日。新环境里齐努力,共建和谐大家庭。” 六年前,由于单位的发展需要,我们从市区搬迁到...
    夏诺xn阅读 440评论 13 18
  • 1.“雷军亲笔作序,小米联合创始人黎万强著。揭开小米4年600亿奇迹背后的理念、方法和案例。了解小米,必读本书!迄...
    Dirac阅读 2,911评论 0 49
  • 我今年大三,22岁。其实我是极其不愿承认这个事实的。我感觉自己一无是处,我感觉自己无法回报多年来一直养着我的家里人...
    d00c63d6777c阅读 250评论 1 0