# 第 11 章 妙用数据结构

# 内容提要

C++ STL
数组
栈和队列
单调栈
优先队列

双端队列
哈希表
多重集合和映射
前缀和与积分图

# 11.1 C++ STL

在刷题时，我们几乎一定会用到各种数据结构来辅助我们解决问题，因此我们必须熟悉各种数据结构的特点。C++ STL 提供的数据结构包括（实际底层细节可能因编译器而异）：

1. Sequence Containers：维持顺序的容器。
   (a). vector：动态数组，是我们最常使用的数据结构之一，用于 O (1) 的随机读取。因为大部分算法的时间复杂度都会大于 O (n)，因此我们经常新建 vector 来存储各种数据或中间变量。因为在尾部增删的复杂度是 O (1)，我们也可以把它当作 stack 来用。
   (b). list：双向链表，也可以当作 stack 和 queue 来使用。由于 LeetCode 的题目多用 Node 来表示链表，且链表不支持快速随机读取，因此我们很少用到这个数据结构。一个例外是经典的 LRU 问题，我们需要利用链表的特性来解决，我们在后文会遇到这个问题。
   (c). deque：双端队列，这是一个非常强大的数据结构，既支持 O (1) 随机读取，又支持 O (1)
   时间的头部增删和尾部增删，不过有一定的额外开销。 (d). array：固定大小的数组，一般在刷题时我们不使用。 (e). forward_list：单向链表，一般在刷题时我们不使用。
2. Container Adaptors：基于其它容器实现的数据结构。
   (a). stack：后入先出（LIFO）的数据结构，默认基于 deque 实现。stack 常用于深度优先搜索、一些字符串匹配问题以及单调栈问题。
   (b). queue：先入先出（FIFO）的数据结构，默认基于 deque 实现。queue 常用于广度优先搜索。
   (c). priority_queue：最大值先出的数据结构，默认基于 vector 实现堆结构。它可以在 O (n log n) 的时间排序数组，O (log n) 的时间插入任意值，O (1) 的时间获得最大值，O (log n) 的时间删除最大值。priority_queue 常用于维护数据结构并快速获取最大或最小值。
3. Associative Containers：实现了排好序的数据结构。
   (a). set：有序集合，元素不可重复，底层实现默认为红黑树，即一种特殊的二叉查找树
   （BST）。它可以在 O (n log n) 的时间排序数组，O (log n) 的时间插入、删除、查找任意值，O (log n) 的时间获得最小或最大值。这里注意，set 和 priority_queue 都可以用于维护数据结构并快速获取最大最小值，但是它们的时间复杂度和功能略有区别，如 priority_queue 默认不支持删除任意值，而 set 获得最大或最小值的时间复杂度略高，具体使用哪个根据需求而定。
   (b). multiset：支持重复元素的 set。

class Solution {

public:

    vector<int> findDisappearedNumbers(vector<int>& nums) {

        vector<int> ve;

        // ve.push_back(2);

        map<int, int> mp;

        for(int i = 0; i < nums.size(); i++) {

            mp[nums[i]] = 1;

        }

        for(int i = 1; i <= nums.size(); i++) {

            if(mp[i] == 0) {

                ve.push_back(i);

            }

        }

        return ve;

    }

};

# 48

class Solution {

public:

    void rotate(vector<vector<int>>& matrix) {

        int temp = 0, n = matrix.size() - 1;

        //i 为循环的圈数，分别思考 n 为奇数和偶数时都用的 n/2 都对的原理

        //j 为循环时上行的横坐标，i 为纵坐标 左上角

        for (int i = 0; i <= n / 2; i++) {

            for(int j = i; j < n - i; j++) {

                //i 代表左上角的位置的横纵坐标

                //i 同时代表横到最上或最下横的距离 或者 纵到最左或最右纵的距离

                temp = matrix[i][j];

                matrix[i][j] = matrix[n- j][i];

                matrix[n- j][i] = matrix[n-i][n-j];

                matrix[n-i][n-j] = matrix[j][n-i];

                matrix[j][n-i] = temp;

            }

        }

    }

};

i 表示一条完整的条，j 表示到条的最左端或者最最上端的距离，当 i 或者 n-i 处在第一维上时，表示横着的条，处在第二维上时表示竖 / 纵着的条，