编码问题记录

  1. 你的代码问题在于:每次拼接字符串时都创建了新对象:
1
new_str = new_str + c;  // ← 每次都创建新字符串,效率极低!

这会导致大量的内存分配和拷贝操作。应该使用 push_back() 或 += 操作符:

LeetCode笔记

1. 队列与栈

1.1 (单调队列) LeetCode.239. 滑动窗口最大值

题目介绍

1
2
3
4
5
题目描述

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7] 
解释：
滑动窗口的位置                最大值

---------------               -----

[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
1
2
3
示例 2：
输入：nums = [1], k = 1
输出：[1]

提示:

  • $1 \le \text{nums.length} \le 10^5$
  • $-10^4 \le \text{nums}[i] \le 10^4$
  • $1 \le k \le \text{nums.length}$

📝 单调队列 (Monotonic Queue)

核心定义：持续维护队列里面的元素单调递增或单调递减的队列。

💡 如何维护单调递减队列？

  • 维护原则：新元素入队前，清除队尾所有比它小的元素。
  • 根本目的：确保队列头部始终是当前窗口的最大值。
  • 底层逻辑：若新元素 x 大于队尾元素 y，则 y 在 x 离开窗口前永无出头之日（既小又老），故可直接删除 y。

📊 演示范例

输入数组：vec = {1, 3, 1, -1, 2}
(注：在此维护下，队列始终保持递减状态)

操作 动作描述 队列状态 (队首 -> 队尾) 当前最大值
push(1) 队空，直接入队 [1] 1
push(3) 3 > 1，弹出 1，入队 3 [3] 3
push(1) 1 < 3，直接入队 [3, 1] 3
push(-1) -1 < 1，直接入队 [3, 1, -1] 3
push(2) 2 > -1 弹出 -1，2 > 1 弹出 1，2 < 3 入队 2 [3, 2] 3
  • 注意：以上演示暂未考虑滑动窗口大小。如果滑动窗口划走的元素恰好是队列的头元素，则需要把头元素移除。
  • 核心洞察：我们本来就不需要维护当前位置之前、且比当前元素更小的元素，因为在当前元素被替换掉之前，那个更小的元素就已经被“干掉”了。

💻 核心代码实现

1. 单调队列类封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class monotonic_queue {
public:
    // 入队：维护单调递减性质
    void push(const int& x) {
        // 如果存入的元素比队尾元素大，则将队尾小于x的元素全部移除
        while(!queue.empty() && queue.back() < x) {
            queue.pop_back(); 
        }
        queue.push_back(x);
    } 

    // 出队：如果要移出的元素正是当前最大值（队首），则弹出队首
    void pop(const int &value) {
        if(!queue.empty() && value == queue.front()) {
            queue.pop_front();
        }
    }

    // 获取当前最大值
    int max() {
        return queue.front();
    }

private:
    deque<int> queue; // 使用双向队列
};

2. 滑动窗口构建逻辑 (Main)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main() {
    monotonic_queue q;
    vector<int> res;
    // 预留空间，避免频繁扩容
    res.reserve(nums.size() - (k - 1));

    // 第一步：先将前 k-1 个元素存入队列
    // 为了保持操作一致性，这里只存 k-1 个元素
    for(int i = 0; i < k - 1; i++) {
        q.push(nums[i]);
    }

    // 第二步：滑动窗口主循环
    // 每次循环执行：①新元素入队 -> ②记录最大值 -> ③移除窗口最左边的元素
    for(int i = k - 1; i < nums.size(); i++) {
        q.push(nums[i]);                 // 新元素入队
        res.push_back(q.max());          // 记录当前窗口最大值
        q.pop(nums[i - (k - 1)]);        // 移除滑出窗口的旧元素
    }
    return res;
}

1.2 (优先级队列(最大最小堆)) LeetCode.347 前 K 个高频元素

题目介绍

类别 难度 喜欢 不喜欢
算法 (Algorithms) 中等 (Medium) 65.72% 2184 -

标签: 哈希表 数组 分治 桶排序 计数 快速选择 排序 堆（优先队列）

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例：

示例 1：

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

示例 2：

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

提示：

  • $1 \le \text{nums.length} \le 10^5$
  • $-10^4 \le \text{nums}[i] \le 10^4$
  • $k$ 的取值范围是 $[1, \text{数组中不相同的元素的个数}]$
  • 题目数据保证答案唯一，换句话说，数组中前 $k$ 个高频元素的集合是唯一的

进阶：

你所设计算法的时间复杂度 必须 优于 $O(n \log n)$ ，其中 $n$ 是数组大小。

📝 优先级队列 (Priority Queue)

核心定义：基于堆 (Heap) 数据结构实现的队列。元素出队顺序不由入队顺序决定，而是由元素的优先级（通常指大小）决定。

💡 如何维护最大堆（默认优先队列）？

  • 核心特性：
    • 非先进先出：元素入队顺序不影响出队顺序。
    • 自动排序：每次插入或删除元素后，内部会自动调整结构，确保堆顶元素始终是优先级最高（最大或最小）的元素。
    • 底层实现：默认使用 std::vector 作为底层容器，通过算法维护堆性质。
  • 维护原则：新元素入队后，通过“上浮”操作调整位置，确保父节点始终大于等于子节点。
  • 底层逻辑：堆是一种完全二叉树结构。对于最大堆，任何节点的值都大于或等于其子节点的值。因此，根节点（top()）必然是全局最大值。插入时只需在末尾添加并向上调整，删除时只需将末尾元素移至根部并向下调整，效率极高。

⚙️ 核心参数与复杂度

1. 模板定义

1
2
3
4
5
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
  • T：存储元素的类型。
  • Container：底层容器，默认为 std::vector<T>。
  • Compare：比较规则，默认为 std::less<T>（即最大堆）。

2. 时间复杂度

  • 插入 (push)： O(log⁡N)
  • 删除堆顶 (pop)： O(log⁡N)
  • 获取堆顶 (top)： O(1)

3. 常用成员函数

函数 描述 复杂度
push(const T& val) 插入元素并调整堆
pop() 删除堆顶元素
top() 返回堆顶元素的引用（不删除）
empty() 判断队列是否为空
size() 返回元素个数

📊 演示范例

输入数组：vec = {1, 3, 1, -1, 2}
(注：这里演示的是 priority_queue<int> 最大堆的入队逻辑)

操作 动作描述 堆内部结构 (逻辑上的完全二叉树) 堆顶 (top)
push(1) 堆空，直接入队 [1] 1
push(3) 3 > 1，3 上浮成为根，1 下沉 [3, 1] 3
push(1) 1 < 3，1 作为左子节点，无需上浮 [3, 1, 1] 3
push(-1) -1 < 1，-1 作为右子节点，无需上浮 [3, 1, 1, -1] 3
push(2) 2 > -1，2 上浮替换 -1；2 > 1? 否，停止 [3, 2, 1, -1, 1] 3
pop() 移除堆顶 3，将末尾 1 移至根，向下调整 [2, 1, 1, -1] 2
  • 注意：priority_queue 底层通常由 vector 实现，它不保证非堆顶元素的有序性，只保证堆顶是极值。

🛠️ 进阶：底层容器 Container 的选择（参数2）

std::priority_queue 的第二个模板参数 Container 指定了底层用于存储数据的容器。它必须支持随机访问迭代器以及 back(), push_back(), pop_back() 操作。

  • 场景 A：追求极致性能（保持默认 vector）
    在 99% 的情况下，不要修改这个参数。std::vector 的连续内存布局使得 CPU 缓存命中率极高，对于堆这种频繁访问父子节点的数据结构，vector 的性能通常优于 deque。
  • 场景 B：避免大规模扩容时的停顿（使用 deque）
    如果数据量极大且不可预测，std::vector 在容量不足时会重新分配内存并复制所有元素，这可能导致短暂的延迟抖动。std::deque 按需分配小块内存，不会发生整体复制。

💻 核心代码实战

1. 基础最大堆与最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <queue>
#include <vector>
#include <functional> // for std::greater

using namespace std;

// 场景1：默认最大堆 (求前K大，或者动态获取最大值)
void example_max_heap() {
    priority_queue<int> maxHeap; 
    
    maxHeap.push(1);
    maxHeap.push(3);
    maxHeap.push(2);
    
    // 输出: 3, 2, 1
    while(!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
}

// 场景2：最小堆 (求前K小，或者维护Top-K大元素时的辅助堆)
void example_min_heap() {
    // 声明方式：priority_queue<Type, Container, Compare>
    // greater<int> 表示小顶堆
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    minHeap.push(1);
    minHeap.push(3);
    minHeap.push(2);
    
    // 输出: 1, 2, 3
    while(!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
}

2. 经典应用：前 K 个高频元素（也就是本题的问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 场景3：解决 "前 K 个高频元素" (结合 Hash Map)
// 思路：统计频率后，维护一个大小为 K 的【最小堆】
// 为什么是最小堆？因为我们要保留最大的 K 个，所以要把小的踢（pop）出去，
// 堆顶就是这 K 个里最小的，方便比较。
vector<int> topKFrequent(vector<int>& nums, int k) {
     unordered_map<int, int> freqMap;
     for(auto & key : nums){
         freqMap[key]++;
     }
     vector<int> res;
     
     // 用小顶堆，堆顶是当前K个元素中频率最小的
     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;

     for(auto & [key, freq] : freqMap) { // key为数字，freq为出现的频率
         minHeap.push(make_pair(freq, key));
         if(minHeap.size() > k){
             minHeap.pop(); // 弹出当前堆内频率最小的那个
         }
     }
     while(!minHeap.empty()){
         res.push_back(minHeap.top().second);
         minHeap.pop();
     }
     return res;
}