Leetcode 150 逆波兰表达式求解
题目链接: 逆波兰表达式求解
给定一个字符串类型的数组，其中按照逆波兰表示法记录了算术表达式，求解该算术表达式最终的结果。
Example 1:Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9Example 2:Input: tokens = ["4","13","5","/","-"]
Output: 6
Explanation: (4 - (13 / 5)) = 2
思路: 由于逆波兰表示法的特性(一次计算由两个数字跟一个算术符号完成)，我们可以利用栈后入先出的特性，每当遇到数字时就压栈，当遇到算术符号时就弹出两个数字进行计算。重复上述操作直至完成数组中所有元素的遍历，随后取出栈中剩下的元素即可。
具体代码实现:
class Solution:def evalRPN(self, tokens: List[str]) -> int:myStack = []operators = '+-*/'for token in tokens:if token not in operators:myStack.append(token)else:num2 = int(myStack.pop())num1 = int(myStack.pop())if token == '+':myStack.append(num1 + num2)elif token == '-':myStack.append(num1 - num2)elif token == '*':myStack.append(num1 * num2)elif token == '/':myStack.append(num1 // num2)return int(myStack.pop())
Leetcode 239 滑动窗口最大值
题目链接: 滑动窗口最大值
给定一个数组 nums 和一个整数 k，大小为 k 的滑动窗口从数组的左侧移动到右侧，一次移动一个单位，返回每次移动时滑动窗口的最大值。
Example 1:Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
思路: 随着滑动窗口的移动，我们的问题关键在于，如何高效地求出一个窗口内的最大值。若通过暴力方法直接遍历窗口找出最大值，则整体时间复杂度为 O(n*k)。我们需要更加高效的方法。
回看题设我们发现，随着滑动窗口的移动，旧的元素被移出滑动窗口，而新的元素被移入滑动窗口，这符合队列的特性，我们可以通过一个队列管理滑动窗口中的元素。进一步进行思考，是否有什么操作能够帮助我们快速找出队列中的最值？答案是单调队列。在向队列中添加元素时，我们维护一个单调队列，这样方便我们快速找出最值。此题中我们使用单调递减队列，这样队头就是当前滑动窗口的最大值。
具体代码实现
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:# 此处采用双向队列而非队列，因为维护单调队列时需要从尾部移除元素from collections import dequeresult = []myQueue = deque(maxlen=k)# 先将前k个元素插入队列中# 再移动滑动窗口，将遍历到的当前数组中的元素插入队列中。# 若当前待插入队列的元素比队列中其前一个元素大，则将前一个元素弹出队列，确保了队列的单调性# 重复此操作，此时队列中队头的元素即为队列中元素最大值for i in range(k):while myQueue and myQueue[-1] < nums[i]:myQueue.pop()myQueue.append(nums[i])result.append(myQueue[0])for i in range(k, len(nums)):# 当队头元素与应当移出滑动窗口的元素相同时，将该元素移出队头if myQueue and nums[i-k] == myQueue[0]:myQueue.popleft()while myQueue and myQueue[-1] < nums[i]:myQueue.pop()myQueue.append(nums[i])result.append(myQueue[0])return result
时间复杂度: O(n)
Leetcode 347 前K个高频元素
题目链接: 前K个高频元素
给定一个数组 nums 找出其中出现的前K个出现频次最高的元素。
Example 1:Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]Example 2:Input: nums = [1], k = 1
Output: [1]
思路: 为了找出给定数组中前K个高频元素，我们需要:
- 统计数组中各个元素出现的频次
- 对频次进行排序
- 找出其中出现的前K个出现频次最高的元素
对于任务1，我们可以通过 map 映射记录各个元素出现的频次。
对于任务2，在具体实现上，我们既可以通过优先级队列对频次进行排序，也可以直接对频次进行排序。
优先级队列是一种抽象数据类型，每个元素带有一个 "优先级"，每次弹出/访问的始终是当前优先级最高/最低的元素。在本题中，由于我们要找的是频率最高的元素，因此此处的优先级为元素出现的频次。优先级队列的具体实现一般为堆(在python中默认为小顶堆)，因为堆从堆头取出元素， 从堆底添加元素，与队列从队头取元素，从队尾添加元素一致。
具体代码实现
# 使用优先级队列求解
from typing import List
import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:myMap = {}for num in nums:myMap[num] = myMap.get(num, 0) + 1prior_queue = []for num, freq in myMap.items():# 插入堆时，将一个二元组(priority, item)插入堆中，此处将元素出现的频次作为优先级heapq.heappush(prior_queue, (freq, num))if len(prior_queue) > k:heapq.heappop(prior_queue)result = [0] * kfor i in range(k-1, -1, -1):result[i] = heapq.heappop(prior_queue)[1] # 倒序取出元素return result
# 使用字典求解
from collections import defaultdict
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:# 首先统计各个元素出现的频次freqMap = {}for num in nums:freqMap[num] = freqMap.get(num, 0) + 1# 随后，再将频次作为key，出现对应次数的元素放在一个数组中，作为valueidxMap = defaultdict(list)for num in freqMap:idxMap[freqMap[num]].append(num)# 对出现的频次进行排序freq = list(idxMap.keys())sortedFreq = sorted(freq)result = []count = 0while count < k:# 将出现频次最高的元素放入结果中，重复这一操作直到找到的元素大于等于k个result.extend(idxMap[sortedFreq[-1]])count += len(idxMap[sortedFreq[-1]])sortedFreq.pop()return result[0:k]
复杂度分析: 时间复杂度: O(nlogn), 空间复杂度: O(n)