代码随想录算法训练营第十三天| 239.滑动窗口最大值、347.前k个高频元素

代码随想录算法训练营第十三天| 239.滑动窗口最大值、347.前k个高频元素

题目

239.滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

from collections import deque
class DiyQueue:
    def __init__(self):
        self.diyQueue = deque()
    
    def diyPop(self, value):
        if self.diyQueue and self.diyQueue[0] == value:
            self.diyQueue.popleft()

    def diyPush(self, value):
        while self.diyQueue and self.diyQueue[-1] < value:
            self.diyQueue.pop()
        self.diyQueue.append(value)

    def getMaxValue(self):
        return self.diyQueue[0]


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        curWindow = DiyQueue()
        res = []
        for i in range(k):
            curWindow.diyPush(nums[i])
        res.append(curWindow.getMaxValue())
        for i in range(k,len(nums)):
            # 因为窗口要滑动，所以删除第一个
            curWindow.diyPop(nums[i-k])
            curWindow.diyPush(nums[i])
            res.append(curWindow.getMaxValue())
        return res

题目

347.前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 用来存储小顶堆的结果
        res = []
        nums2frq = {}
        for i in range(len(nums)):
            nums2frq[nums[i]] = nums2frq.get(nums[i], 0) + 1
        
        for key, freq in nums2frq.items():
            heapq.heappush(res, (freq, key))
            if len(res) > k:
                heapq.heappop(res)
        
        result = [0] * k
        for i in range(k-1,-1,-1):
            result[i] = heapq.heappop(res)[1]
        return result