代码随想录算法训练营day11|150. 逆波兰表达式求值 239. 滑动窗口最大值 347.前 K 个高频元素

from operator import add, sub, mul

def div(x, y):
    return int(x/y) if x*y > 0 else -(abs(x)//abs(y))

class Solution(object):
    op_map = {'+':add, '-':sub, '*':mul, '/':div}
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack=[]
        for token in tokens:
            if token not in self.op_map:
                stack.append(int(token))
            else:
                op2=stack.pop()
                op1=stack.pop()
                stack.append(self.op_map[token](op1, op2))
        return stack.pop()

from collections import deque

class MyQuee:
    """
    自定义单调队列，包括他的入队和出队的规则
    """
    def __init__(self):
        self.queue = deque()
    
    # value出：若队列不为空，且该值等于头元素，则可出 （反正出的都是此时的最大值）
    def pop(self, value):
        if self.queue and value==self.queue[0]:
            self.queue.popleft()

    # value入：若队不为空，且该值大于队尾值，则循环删除队尾值，最后把该值加到队尾 （保证队列单调递减）
    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(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        que = MyQuee()
        result = []
        for i in range(k):
            que.push(nums[i])        # 调用自定义入队方式
        result.append(que.front())   # 调用自定义取出最大值方式
        for i in range(k, len(nums)):
            que.pop(nums[i-k])       # 调用自定义出队方式，来移除滑动窗格离开的那个元素
            que.push(nums[i])         # 调用自定义入队方式，来添加滑动窗格移入的那个元素
            result.append(que.front()) # 调用自定义取最大值方式，并把最大值保持到结果中
        return result

import heapq      # 优先级队列，默认最小堆
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # 统计（值：频次）
        map_ = {}
        for i in range(len(nums)):
            map_[nums[i]] = map_.get(nums[i], 0)+1

        # 我猜是把新键值对加入最小堆，再把前k个以外的都弹出，（在最小堆里，就是把根那部分弹出去）
        priority_que = []
        for key, freq in map_.items():
            heapq.heappush(priority_que, (freq, key))
            if len(priority_que) > k:
                heapq.heappop(priority_que)
        
        # 因为小顶堆是先弹出最小的，这里专门倒序来输出数组
        result = [0]*k
        for i in range(k-1, -1, -1):
            result[i] = heappop(priority_que)[1]
        return result