239.滑动窗口最大值
239. 滑动窗口最大值 - 力扣（LeetCode）
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
- 示例 1：
- 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
- 输出：[3,3,5,5,6,7]
- 解释：
- 滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
- 示例 2：
- 输入：nums = [1], k = 1
- 输出：[1]
解题思路
单调队列：先形成窗口，若队列尾部元素<当前元素，则剔除尾部元素；再从k处遍历列表，若队列头部元素==窗口第一个元素，则剔除队列头部元素；再判断队列尾部元素<当前元素，剔除尾部元素；最后，将当前元素添加到队列，并将队列头部元素添加至result中
from collections import deque
class Solution():
def maxSlidingWindow(self,nums,k):
if not nums or not k or len(nums)<k: return []
queue = deque()
for i in range(k):
while queue and queue[-1]<nums[i]:
queue.pop()
queue.append(nums[i])
result = [queue[0]]
for j in range(k,len(nums)):
if queue[0]==nums[j-k]:
queue.popleft()
while queue and queue[-1]<nums[j]:
queue.pop()
queue.append(nums[j])
result.append(queue[0])
return result
347.前K个高频元素
347. 前 K 个高频元素 - 力扣（LeetCode）
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
- 示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
- 示例 2:
- 输入: nums = [1], k = 1
- 输出: [1]
解题思路
hashmap：先用dict存储nums中的元素及出现次数，将dict转化成二维list，再对二维list按出现次数排序(sorted+lambda)，取前k个list，最后取出前k个元素并组装
class Solution:
def topKFrequent(self,nums,k):
dic = {}
for i in nums:
dic[i] = dic.get(i,0)+1
th_list = [[k,v] for k,v in dic.items()]
th_list_sort = sorted(th_list,key=lambda x:x[1],reverse=True)
result = [th_list_sort[i][0] for i in range(k)]
return result