代码随想录算法训练营第十一天|239. 滑动窗口最大值,347.前 K 个高频元素,总结

发布时间:2024年01月22日

系列文章目录

代码随想录算法训练营第一天|数组理论基础,704. 二分查找,27. 移除元素
代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II
代码随想录算法训练营第三天|链表理论基础,203.移除链表元素,707.设计链表,206.反转链表
代码随想录算法训练营第四天|24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交,142.环形链表II,总结
代码随想录算法训练营第五天|哈希表理论基础,242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1. 两数之和
代码随想录算法训练营第六天|454.四数相加II,383. 赎金信,15. 三数之和,18. 四数之和,总结
代码随想录算法训练营第七天|344.反转字符串,541. 反转字符串II,卡码网:54.替换数字,151.翻转字符串里的单词,卡码网:55.右旋转字符串
代码随想录算法训练营第八天|28. 实现 strStr(),459.重复的子字符串,字符串总结,双指针回顾
代码随想录算法训练营第九天|理论基础,232.用栈实现队列,225. 用队列实现栈
代码随想录算法训练营第十天|20. 有效的括号,1047. 删除字符串中的所有相邻重复项,150. 逆波兰表达式求值


239. 滑动窗口最大值

题目链接: 239.滑动窗口最大值
题目内容: 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
视频讲解:单调队列正式登场!| LeetCode:239. 滑动窗口最大值

核心思想:自行构建一个单调队列,在将大小为k的滑动窗口中元素放进队列中时,如果元素比当前队列中元素值都大,那么就弹出前边的元素,确保当前队列的最外端的元素始终为窗口的最大值。

from collections import deque

class MyQueue:
    def __init__(self):
        self.queue=deque()#直接使用list会超时
    
    def pop(self,value):
        if self.queue and value==self.queue[0]:
            self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()
    
    def push(self,value):
        while self.queue and value>self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)

    def front(self):
        return self.queue[0] 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue=MyQueue()
        result=[]
        for i in range(k):
            queue.push(nums[i])
        result.append(queue.front())
        for i in range(k,len(nums)):
            queue.pop(nums[i-k])
            queue.push(nums[i])
            result.append(queue.front())
        return result
        

347.前 K 个高频元素

题目链接: 347.前k个高频元素
题目内容: 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
视频讲解:优先级队列正式登场!大顶堆、小顶堆该怎么用?| LeetCode:347.前 K 个高频元素

核心思想:使用map来进行统计元素出现的频率,使用优先级队列对频率进行排序

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        #要统计元素出现频率
        map_ = {} #nums[i]:对应出现的次数
        for i in range(len(nums)):
            map_[nums[i]] = map_.get(nums[i], 0) + 1
        
        #对频率排序
        #定义一个小顶堆,大小为k
        pri_que = [] #小顶堆
        
        #用固定大小为k的小顶堆,扫描所有频率的数值
        for key, freq in map_.items():
            heapq.heappush(pri_que, (freq, key))
            if len(pri_que) > k: #如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k
                heapq.heappop(pri_que)
        
        #找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组
        result = [0] * k
        for i in range(k-1, -1, -1):
            result[i] = heapq.heappop(pri_que)[1]
        return result

总结

  1. 用栈实现队列,用队列实现栈来掌握的栈与队列的基本操作;
  2. 栈在系统中的应用及使用技巧:括号匹配问题、字符串去重问题、逆波兰表达式问题;
  3. 单调队列和优先级队列:滑动窗口最大值、前K个高频元素
文章来源:https://blog.csdn.net/weixin_47748259/article/details/135742111
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。