代码随想录算法训练营 Day 10

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if t not in {'+', '-', '*', '/'}:
                stack.append(int(t))
            else:
                n2 = stack.pop()
                n1 = stack.pop()
                if t == '+':
                    res = n1 + n2
                elif t == '-':
                    res = n1 - n2
                elif t == '*':
                    res = n1 * n2
                else:
                    res = int(n1 / n2)
                stack.append(res)
        
        return stack.pop()

from collections import deque

# 实现单调队列
# 保证了队列中的元素是按照从大到小排列的
class myDeque:
    def __init__(self):
        self.queue = deque()

    def pop(self, val):
        if self.queue and self.queue[0] == val:
            self.queue.popleft()
    
    def push(self, val):
        # 当前元素本来应该加在栈尾，但如果栈中前面的元素比它小，则直接将其出栈，直到为空或者栈尾元素比当前值大
        while self.queue and self.queue[-1] < val:
            self.queue.pop()
        self.queue.append(val)
        
    def peek(self):
        # 保证了当前栈首一定为最大元素
        return self.queue[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        q = myDeque()
        for i in range(k):
            q.push(nums[i])
        res.append(q.peek())

        for i in range(k, len(nums)):
            q.pop(nums[i - k])
            q.push(nums[i])
            res.append(q.peek())
        
        return res

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hashmap = {}
        for num in nums:
            hashmap[num] = hashmap.get(num, 0) + 1
        
        queue = []
        for n, f in hashmap.items():
            heapq.heappush(queue, (f, n))
            if len(queue) > k:
                heapq.heappop(queue)
        
        res = []
        for f, n in queue:
            res.append(n)

        return res