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

150. 逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入: ["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]
输出: 22

解释:该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
= ((10 * (6 / (12 * -11))) + 17) + 5       
= ((10 * (6 / -132)) + 17) + 5     
= ((10 * 0) + 17) + 5     
= (0 + 17) + 5    
= 17 + 5    
= 22

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

思路：由于很久之前就接触过，不是第一次做，第一反应就是要用栈，不意外的很快就有思路了。逆波兰在依次遍历所给数组时，当遇到数字时，可以直接将数字压入栈，但这里需要注意的是，首先所给的数字是字符，需要先转换为int类型后再压入栈；其次是需要注意数字有可能是负数，也是我第一次debug遇到的问题，遇到负数的时候，先确定运算是否支持负数的运算，确定支持后直接将负数压入栈即可。

而当遍历到符号的时候，不需要入栈，直接判断是加减乘除哪一种运算，由于案例给的是先入栈的数字作为第一运算符，栈顶的数字作为第二运算符，按照所给的过程进行运算即可。

补充资料：

负数是否能够被isdigit()检测出来呢？

不会的。isdigit() 方法只检测字符串是否由数字组成，并且不包含任何其他字符。对于 -11 这样的字符串，isdigit() 方法会返回 False，因为其中包含了负号 -。

如果你需要处理可能包含负号的整数字符串，你可以使用 str.isdigit() 来检查字符串是否只包含数字，然后根据需要进行处理。

代码实现如下：

class Solution:

    def evalRPN(self, tokens: List[str]) -> int:

        sta = []

        for i in range(len(tokens)):

            if tokens[i].isdigit():

                sta.append(int(tokens[i]))

            elif tokens[i] == '+':

                b = int(sta.pop())

                a = int(sta.pop())

                sta.append(a+b)

            elif tokens[i] == '-':

                b = int(sta.pop())

                a = int(sta.pop())

                sta.append(a-b)

            elif tokens[i] == '*':

                b = int(sta.pop())

                a = int(sta.pop())

                sta.append(a*b)

            elif tokens[i] == '/':

                b = int(sta.pop())

                a = int(sta.pop())

                sta.append(a/b)

            else: # 考虑负数的情况

                sta.append(int(tokens[i]))

        return int(sta.pop())

提供规范代码，可以直接使用内置的运算函数：

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: List[str]) -> int:

        stack = []

        for token in tokens:

            if token not in {'+', '-', '*', '/'}:

                stack.append(int(token))

            else:

                op2 = stack.pop()

                op1 = stack.pop()

                stack.append(self.op_map[token](op1, op2))  # 第一个出来的在运算符后面

        return stack.pop()

239. 滑动窗口最大值

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

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

进阶：

你能在线性时间复杂度内解决此题吗？

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

思路：

一开始理解错题意，以为是返回最大的窗口和，以为只要每次pop和push的时候判断进出的两个值大小即可。还是比较粗心了。。

后来理解题意后，也只能想到暴力两次遍历了，还是选择参考一下代码随想录的文字解析。

提供了一个单调队列的方法，尝试用自己的语言复述一遍：

在窗口进行滑动的时候，判断离开窗口的元素是否在单调队列中，如果在则将其在队列中弹出，否则不关注离开窗口的元素。然后判断进入窗口的新元素是否会成为窗口中的最大值，此时在队列中的元素一定是窗口内的元素，但是窗口内的元素不一定都在队列中，只有窗口内的最大值或者依次递减下来的其他元素（有没有其他元素取决于这些第二大的元素是否在最大值之后，满足递减队列的要求），所以新进入的元素就需要与队列中最小的元素开始依次比较，直到找到自己在队列中的位置，但如果遇到比本元素小的元素需要将其剔除队列中。这样我们就保持让队列中存在的元素都是窗口内的最大值和最大值替补。

单调队列在不同题目中可以有不同的含义，最重要的是使用者怎么使用。在本题中，目的是让队列头始终是队列里的最大值，因为只有这样我们才能返回滑动窗口的最大值，即使这个最大值在窗口滑动的过程中被弹出时，剩下的队列中依然是单调递减的，这样就确保了弹出后位于队列头位置的数依然是队列里的最大值。

实现上，需要自定义一个队列，以便于实现以上过程需要的功能。首先，这个队列需要有明确的，pop，push，front三个功能，用于弹出、压入、以及返回队列头的最大值。

Pop：附上弹出元素这一参数，弹出前，确保队列中是非空的，同时判断弹出元素是否位于队列头部（这是因为弹出的元素是在给的数组中直接选择的，并不一定在我们设置的队列中，所以需要有判断是否相等的这一步）。

Push：附上压入元素这一参数，压入前，首先判断压入的元素与当前队列尾部（这里第一次写很容易与队列头部的最大值比较，但我们只是需要确保队列单调，只需要反复与队列尾部进行比较，如果比最大值大，最终也会将最大值弹出，否则也能将比压入元素小的所有元素都弹出，确保队列是单调递减）谁大，如果大于当前队尾元素，则弹出队尾。直到不能弹出后，将压入元素push进队列中。

Front：直接返回当前队列的最大值即可，即队列头部位置元素。

根据以上理解，自己复现代码实现如下：

from collections import deque





class Myque:

    def __init__(self):

        self.que = deque()



    def pop(self, value):

        if self.que and self.que[0]==value: # 非空且存在该元素

            self.que.popleft()



    def push(self, value): # 非空且队尾元素小于压入元素时弹出，确保队列是单调队列

        while self.que and self.que[-1] < value:

            self.que.pop()

        self.que.append(value)



    def front(self): # 直接返回队列头部

        return self.que[0]



class Solution:

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        que = Myque()

        i = 0

        res = []

        while i < k:

            que.push(nums[i])

            i += 1

        res.append(que.front())

        while i < len(nums):

            que.pop(nums[i-k])

            que.push(nums[i])

            res.append(que.front())

            i += 1

        return res

与规范代码相比，实现基本一致，还是附上供借鉴学习：

from collections import deque



class MyQueue: #单调队列（从大到小

    def __init__(self):

        self.queue = deque() #这里需要使用deque实现单调队列，直接使用list会超时

    

    #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。

    #同时pop之前判断队列当前是否为空。

    def pop(self, value):

        if self.queue and value == self.queue[0]:

            self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()

            

    #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。

    #这样就保持了队列里的数值是单调从大到小的了。

    def push(self, value):

        while self.queue and value > self.queue[-1]:

            self.queue.pop()

        self.queue.append(value)

        

    #查询当前队列里的最大值 直接返回队列前端也就是front就可以了。

    def front(self):

        return self.queue[0]

    class Solution:

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        que = MyQueue()

        result = []

        for i in range(k): #先将前k的元素放进队列

            que.push(nums[i])

        result.append(que.front()) #result 记录前k的元素的最大值

        for i in range(k, len(nums)):

            que.pop(nums[i - k]) #滑动窗口移除最前面元素

            que.push(nums[i]) #滑动窗口前加入最后面的元素

            result.append(que.front()) #记录对应的最大值

        return result

347.前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案

思路：统计出现的整数频数第一反应想到的肯定使用字典统计。统计完后想到的是先将频数放入数组中，然后排序，接着返回最后k个数值。再将这k个数值对应的key值添加到列表中。

错误实现如下（这个方法考虑不到相同数字出现相同频率的情况，如[1,2]，k=2，这样最大的两个数刚好都是为1，所以只会出现一个数。这里只保存了最后一次出现的数字，如果有多个数字具有相同的出现次数，之前的数字会被覆盖）：

class Solution:

def topKFrequent(self, nums: List[int], k: int) -> List[int]:

dict = {}

for i in range(len(nums)):

dict[nums[i]] = dict.get(nums[i], 0) + 1

dict2 = {}

for num in dict:

dict2[dict[num]] = num

arr = list(dict2.keys())

arr.sort()

j = 0

res = []

while j < k and arr:

cur = arr.pop()

res.append(dict2[cur])

j += 1

return res

使用defaultdict可以很好的解决这个问题：在Python中，defaultdict 是 collections 模块提供的一个非常有用的类，它继承自标准的 dict 类。defaultdict 的特殊之处在于它为字典提供了一个默认值工厂，这个工厂会在尝试访问不存在的键时自动创建一个默认值。

当你创建一个 defaultdict 时，你需要提供一个函数（通常是一个数据类型的构造函数，如 list、set 等）作为第一个参数。这个函数被称为默认工厂函数，它负责生成默认值。对于 list 这个默认工厂函数，当尝试访问一个不存在的键时，defaultdict 会自动创建一个空列表，并允许你对这个空列表进行操作，如 append、extend 等。

在Python中，append 和 extend 是两个用于向列表添加元素的方法，但它们在功能和用途上有所不同。

append()

append() 方法用于将一个对象添加到列表的末尾。
它添加的对象是一个单独的元素，而不是多个元素的序列。
当添加的对象是另一个列表时，它将整个列表作为单个元素添加到列表末尾。

extend()

extend() 方法用于一次性将一个迭代器（如列表、元组、字符串等）中的所有元素添加到列表的末尾。
它用于扩展列表，而不是添加单个元素。

修正代码如下：

from collections import defaultdict



class Solution:

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        if k == len(nums):

            return nums

        dict = defaultdict(list)

        for i in range(len(nums)):

            dict[nums[i]] = dict.get(nums[i], 0) + 1

        dict2 = defaultdict(list)

        for num in dict:

            dict2[dict[num]].append(num) # 相同频数的数字会成为一个数组，在后面输出结果的时候extend入结果数组中

        arr = list(dict2.keys())

        arr.sort()

        j = 0

        res = []

        while j < k and arr:

            cur = arr.pop()

            res.extend(dict2[cur]) # 注意要用extend不能用append

            j += 1

        return res[:k]

规范代码有一思路一致的方法，记录以供对比学习：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 使用字典统计数字出现次数
        time_dict = defaultdict(int)
        for num in nums:
            time_dict[num] += 1
        # 更改字典，key为出现次数，value为相应的数字的集合
        index_dict = defaultdict(list)
        for key in time_dict:
            index_dict[time_dict[key]].append(key)
        # 排序
        key = list(index_dict.keys())
        key.sort()
        result = []
        cnt = 0
        # 获取前k项
        while key and cnt != k:
            result += index_dict[key[-1]]
            cnt += len(index_dict[key[-1]])
            key.pop()

        return result[0: k]

另提供代码随想录规范代码，方法是使用小顶堆的方式，感觉这个方法更契合该题考察的角度。

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。

为什么不用快排呢，使用快排要将map转换为vector的结构，然后对整个数组进行排序，而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。

此时要思考一下，是使用小顶堆呢，还是大顶堆？

有的同学一想，题目要求前 K 个高频元素，那么果断用大顶堆啊。

那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。

而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？

所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

代码如下：

#时间复杂度：O(nlogk)#空间复杂度：O(n)import heapqclass 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

以上用到了heapq，补充一下基础知识：

在Python中，heapq 是一个提供堆队列算法的模块，通常用于实现优先队列。堆是一种特殊的二叉树，其中每个父节点的值都小于或等于其子节点的值（在最小堆中）或大于或等于其子节点的值（在最大堆中）。Python的 heapq 模块默认实现了最小堆。