LeetCode-栈与优先队列算法技巧总结

VocabVictor2024-09-022024-09-04

引言

栈和优先队列是两种重要的数据结构，在算法设计和问题解决中扮演着关键角色。本文将深入探讨这两种数据结构的概念、实现方法、应用场景以及相关的解题技巧。

1. 栈（Stack）

1.1 基本概念

栈是一种遵循后进先出（LIFO, Last-In-First-Out）原则的线性数据结构。主要操作包括：

push：将元素压入栈顶
pop：移除并返回栈顶元素
peek/top：返回栈顶元素但不移除
isEmpty：检查栈是否为空

1.2 Python 实现

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

1.3 应用场景

函数调用栈
表达式求值
括号匹配
深度优先搜索（DFS）
撤销操作

1.4 解题技巧

单调栈: 用于解决下一个更大元素、直方图最大矩形等问题。

def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []
    for i in range(len(nums) - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(nums[i])
    return result

辅助栈: 如最小栈问题，使用辅助栈来跟踪最小值。

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

2. 优先队列（Priority Queue）

2.1 基本概念

优先队列是一种特殊的队列，其中的元素都有一个优先级。高优先级的元素会被优先处理。主要操作包括：

enqueue：插入元素
dequeue：移除并返回最高优先级的元素
peek：返回最高优先级的元素但不移除

2.2 Python 实现（使用堆）

Python 的 heapq 模块提供了优先队列的功能：

import heapq

class PriorityQueue:
    def __init__(self):
        self.elements = []

    def enqueue(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def dequeue(self):
        return heapq.heappop(self.elements)[1]

    def peek(self):
        return self.elements[0][1]

    def is_empty(self):
        return len(self.elements) == 0

    def size(self):
        return len(self.elements)

2.3 应用场景

Dijkstra’s 最短路径算法
任务调度
数据压缩（Huffman编码）
事件驱动模拟
中位数维护

2.4 解题技巧

Top K 问题: 使用最小堆来维护 K 个最大元素。

import heapq

def top_k(nums, k):
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap

多路归并: 使用优先队列来高效合并多个有序列表。

import heapq

def merge_k_sorted_lists(lists):
    merged = []
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)

    while heap:
        val, list_index, element_index = heapq.heappop(heap)
        merged.append(val)
        if element_index + 1 < len(lists[list_index]):
            next_element = lists[list_index][element_index + 1]
            heapq.heappush(heap, (next_element, list_index, element_index + 1))

    return merged

3. 栈与优先队列的比较

特性	栈	优先队列
插入顺序	LIFO	基于优先级
删除元素	始终是栈顶元素	最高优先级元素
实现难度	简单	相对复杂
时间复杂度	O(1) 插入和删除	O(log n) 插入和删除
主要应用	DFS、表达式求值	Dijkstra算法、任务调度