1. 综述

1. 定义

数据结构

数据结构是计算机存储、组织数据的方式，包含逻辑结构与物理结构：

逻辑结构描述元素间的抽象关系，分为集合、线性、树形、图形结构
物理结构描述数据在内存中的实际分布，分为顺序存储与链式存储

算法

算法是解决特定问题的有限执行步骤，具备有穷性、确定性、可行性，并拥有输入与输出

2. 复杂度

程序运行需要计算时间和存储空间两种资源，算法对这两种资源的使用程度可以用来衡量该算法的优劣：

时间复杂度：程序运行需要的计算时间
空间复杂度：程序运行需要的存储空间

大 $\mathbf{O}$ 表示法用来表示算法在最坏情况下的渐进时空复杂度。它忽略了常数因子和低阶项，只关注最高阶部分，用于衡量随着输入数据 $n$ 的增长，算法消耗时空资源的增长趋势

3. 分类

基于逻辑结构分类：

集合结构

元素同属一个集合，元素彼此无顺序、层次或连通关系
线性结构

元素之间存在严格的一对一关系。每个元素（除首尾外）有且仅有一个直接前驱和一个直接后继
树形结构

元素之间存在一对多的层次关系。除根结点外，每个结点有且仅有一个直接前驱，可以有多个直接后继
图形结构

元素之间存在多对多的任意关系。任何结点都可以有多个前驱和多个后继

从物理结构看，只有两种原子存储方式：使用连续空间的顺序存储和使用指针的链式存储。其余所有的物理实现，都是这两种方式的组合。

2. 线性结构

线性结构按照操作是否受限又可分为通用线性结构和受限线性结构两大类。

通用线性结构亦可统称为线性表，长度动态可变，支持在任意位置插入、删除和随机访问。受限的线性结构包括栈、队列、字符串等。

1. 线性表

线性表可记为 $L = (a_1, a_2,…, a_n)$ ，其中 $n \geq 0$ ， $n = 0$ 时为空表

根据存储方式的不同，线性表可以分别通过数组和链表来实现

在 STL 中 std::vector 是使用动态数组实现的线性表，std::list 是使用双向链表实现的线性表。

Josephus Problem I

Consider a game where there are n children (numbered $1,2,…,n$ ) in a circle. During the game, every second child is removed from the circle, until there are no children left. In which order will the children be removed?

Input

The only input line has an integer n.

Constraints: $1 \leq n \leq 2·10^5$

Output

Print $n$ integers: the removal order.

Example

1 2	Input: 7 Output: 2 4 6 1 5 3 7

考虑一个游戏，有 $n$ 个孩子（编号为 $1, 2, \dots, n$ ）围成一个圈。游戏过程中，每隔一个孩子就将其从圈子中移出，直到不剩任何孩子为止。请问孩子们被移出的顺序是什么？

输入

唯一的输入行包含一个整数 $n$

数据范围： $1 \le n \le 2 \cdot 10^5$

输出

输出 $n$ 个整数：即孩子被移出的顺序

很容易想到，可以用一个线性表来模拟这个过程；因为孩子的总数是 $n$ ，所以显然我们需要移除 $n$ 次，每次移除时我们需要计算出隔一位孩子的位置。

#include <iostream>
#include <vector>
#include <numeric>

constexpr int step = 2;

int main() 
{
	int n{ 0 };
	std::cin >> n;

	std::vector<int> children(n);
	std::iota(children.begin(), children.end(), 1); // 直接填入 1 ~ n

	int pos = 0;
	for (int i = 0; i < n; ++i)
	{
		pos = (pos + step - 1) % children.size();
		std::cout << children[pos] << " ";
		children.erase(children.begin() + pos);
	}

	return 0;
}

这段代码虽然逻辑正确，但 std::vector 的 erase 是一个线性复杂度的操作，循环执行了 $n$ 次，所以时间复杂度是 $\mathbf{O(n^2)}$

使用 <numeric> 头文件中的 std::iota 可以用来直接填充递增序列

既然 erase 需要移动内存效率低下，那我们可以不执行真正的删除。如果我们将走完一圈视作一轮，那么每一轮剩下孩子的规模都将减半。模拟这个过程中记录当前轮次参与游戏的孩子和游戏后剩下的孩子，那么剩下的孩子将是下一轮参与游戏的孩子。不断重复此过程亦可得到正确的序列，而不必真正将数据从数组中移除。

#include <iostream>
#include <vector>
#include <numeric>

constexpr int step = 2;

int main() 
{
	int n{ 0 };
	std::cin >> n;

	std::vector<int> curRound(n);
	std::iota(curRound.begin(), curRound.end(), 1);

	std::vector<int> nextRound;
	nextRound.reserve(n / 2 + 1);

	bool isDelete = false; // 状态交替标志位
	while (!curRound.empty())
	{
		for (const int child : curRound)
		{
			if (isDelete)
			{
				std::cout << child << " ";
			}
			else
			{
				nextRound.emplace_back(child);
			}
			isDelete = !isDelete;
		}
		curRound = std::move(nextRound);
		nextRound.clear();
	}

	return 0;
}

每轮游戏数组的长度都减半，总计算量： $n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots \le 2n$ ，因此时间复杂度为 $\mathbf{O(n)}$

std::vector 的 reverse 和 resize 的区别在于前者只分配空间，不创建元素，只改变了 capacity，而未改变 size；而后者改变了元素个数 size

约瑟夫问题

$n$ 个人围成一圈，从第一个人开始报数，数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号

输入

两个整数 $n,m$ ， $1 \le m, n \le 100$

输出

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

example

1 2	input: 10 3 output: 3 6 9 2 7 1 8 5 10 4

这是完整版的经典约瑟夫问题，它不再是每隔一个人移除一次，而是每隔任意个移除一次。上一题的第二种方法将不再适用，它强依赖于“保留一个、删除一个”的严格交替性质。

但我们依然可以使用线性表来到达“模拟删除，而不真正删除”的优化效果。具体来说，可以使用数组模拟循环链表：

#include <iostream>
#include <vector>

int main()
{
	int n{ 0 }, k{ 0 };
	std::cin >> n >> k;

	std::vector<int> next(n + 1);
	for (int i = 1; i < n; ++i)
	{
		next[i] = i + 1;
	}
	next[n] = 1;

	int cur = 1, prev = n;
	while (cur != next[cur])
	{
		for (int step = 0; step < k - 1; ++step)
		{
			prev = cur;
			cur = next[cur];
		}
		std::cout << cur << " ";
		next[prev] = next[cur];
		cur = next[cur];
	}

	std::cout << cur;
	return 0;
}

想象 $n$ 个孩子围成一圈。代码里定义了一个数组 next，next[i] 的含义就是：“编号为 i 的孩子的下一个人是谁”。让每个孩子都指向他右手边的下一个人，而最后一个孩子 next[n] = 1 指回第一个人。在逻辑上构成了首尾相接的圆环。

for (int step = 0; step < k - 1; ++step) 
{
    prev = cur;
    cur = next[cur];
}

这个 for 循环就是报数的过程。我们要找到第 $k$ 个孩子，只需要让 cur 沿着环向前走 $k-1$ 步，同时 prev 紧跟其后。而 next[prev] = next[cur] 让被淘汰者的前一个人，直接指向他的后一个人，相当于淘汰者直接被删除了，再也没有任何人能链接到他。cur = next[cur] 让当前指针跳到下一个人，准备下一轮游戏。当圈子里只剩一个人时，他的下一个人就是他自己，即 cur == next[cur]，此时 while 循环终止。

该算法时间复杂度为 $\mathbf{O(n \cdot m)}$

经典约瑟夫问题又很多不同解法，问题本身也有不同的版本，将在后续的内容中谈到

2.栈

栈（Stack）是限制仅在表尾进行插入和删除操作的线性表。

把允许操作的一端称为栈顶，固定的一端称为栈底。当表中不含任何元素时称为空栈。栈的修改遵从后进先出的原则。

在 STL 中，栈对应 std::stack。但它并不是一个全新的容器，而是一种容器适配器（Container Adapter），是对已有容器（如 std::deque、std::vector、std::list）的包装，使其表现出后进先出的栈行为。可以使用模板参数指定具体容器。

1	template <class _Ty, class _Container = deque<_Ty>> class stack;

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

example

input: s = "()"
output: true

input: s = "()[]{}"
output: true

input: s = "(]"
output: false

input: s = "([)]"
output: false

首先建立左右括号的映射关系，然后扫描字符串，遇到左括号直接入栈。遇到右括号需要先判断栈非空，然后取栈顶元素看是否和当前右括号匹配即可：

class Solution 
{
public:
    bool isValid(string s) 
    {
        unordered_map<char, char> relateMap =
        {
	        {'(', ')'},
	        {'[', ']'},
	        {'{', '}'},
        };

        stack<char> charStack;
        for (const auto& ch : s)
        {
	        if (relateMap.count(ch))
	        {
		        charStack.push(ch);
	        }
	        else
	        {
                if(charStack.empty())
                {
                    return false;
                }
		        auto& curTop = charStack.top();
		        if (relateMap[curTop] == ch)
		        {
			        charStack.pop();
		        }   
		        else
		        {
			        return false;
		        }
	        }
        }       

        return charStack.empty();
    }
};

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

input: temperatures = [73,74,75,71,69,72,76,73]
output: [1,1,4,2,1,1,0,0]

input: temperatures = [30,40,50,60]
output: [1,1,1,0]

input: temperatures = [30,60,90]
output: [1,1,0]

此题最简单的解法是暴力解法，对于每个索引，往后寻找到下一个更高的温度即可，但其复杂度是 $\mathbf{O(n^2)}$ ，很显然会超时：

class Solution
{
public:
    vector<int> dailyTemperatures(vector<int>& temperatures)
    {
        vector<int> res(temperatures.size(), 0);
        for (int i = 0; i < temperatures.size(); ++i)
        {
            int curVal = temperatures[i];
            for(int j = i + 1; j < temperatures.size(); ++j)
            {
                if(temperatures[j] > curVal)
                {
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }
};

同时这是一个典型的单调栈问题。

遍历温度表，对于温度表的每个索引，维护一个单调栈，如果栈为空或者当前温度小于等于栈顶温度，就继续将当前温度的索引入栈。

如果当前温度大于栈顶温度，那么就执行出栈操作，直到当前温度是栈中最大（栈恢复单调性）或者栈空。每个出栈的结果为当前索引减去栈顶索引。

class Solution
{
public:
    vector<int> dailyTemperatures(vector<int>& temperatures)
    {
        vector<int> res(temperatures.size(), 0);
        stack<int, vector<int>> tempStack;

        for (int i = 0; i < temperatures.size(); ++i)
        {
            int curVal = temperatures[i];
            if (tempStack.empty() || curVal <= temperatures[tempStack.top()])
            {
                tempStack.push(i);
            }
            else
            {
                while (!tempStack.empty() && curVal > temperatures[tempStack.top()])
                {
                    res[tempStack.top()] = i - tempStack.top();
                    tempStack.pop();
                }
                tempStack.push(i);
            }
        }

        return res;
    }
};

在上面的代码中直接使用 std::stack 作栈，但std::stack 默认底层是 deque，内存不连续，所以显式指定了底层容器为 std::vector<int> 可以显著提高效率。直接使用 std::vector<int> 甚至静态数组亦可提高效率。

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

1 <= heights.length <=105
0 <= heights[i] <= 104

example

input：heights = [2,1,5,6,2,3]
output：10
    
input：heights = [2,4]
output：4

首先容易想到的是暴力解法。假设先固定一根柱子，假设它是最终矩形里最矮那一根，那么它所决定的最大矩形就是左右两边第一根比它矮的柱子所围成的区域（不包含比它矮的柱子）。然后对每根柱子求出最大矩形，最后在所有矩形中取最大值。其复杂度是 $\mathbf{O(n^2)}$ ，会超时。

值得注意的是这里 left 和 right 的计算，它们最终都指向的索引是比当前柱子更矮那一根的索引，即便数组中没有更矮的柱子，也是一个越界的值。即最终要计算的区域始终被 left 和 right 所真包含，所以 width 可以用 right - left -1 统一计算得出。

class Solution
{
public:
    int largestRectangleArea(vector<int>& heights)
    {
        int maxArea{ 0 };
        for (int i = 0; i < heights.size(); ++i)
        {
            int curHeight = heights[i];

            int left = i;
            while (left >= 0 && heights[left] >= curHeight)
            {
                --left;
            }

            int right = i;
            while (right <= heights.size() - 1 && heights[right] >= curHeight)
            {
                ++right;
            }

            int width = right - left - 1;
            maxArea = max(maxArea, width * curHeight);
        }

        return maxArea;
    }
};

更好的解法是使用单调栈。

在遍历过程中，维护一个栈，里面存柱子的下标，并且栈中柱子的对应高度保持单调递增。如果遇到一个比栈顶更矮的柱子时，以栈顶柱子为高度的矩形右边界就确定了，为当前下标 i，弹出栈顶柱子，弹出后新的栈顶就是其左边界。计算矩形面积。

持续这个过程，直到栈中的柱子都比 i 对应的柱子矮。然后就可将当前柱子入栈。

值得注意的是，我们的右边界和右边界仍然都是将矩形真包含的。所以当 i 大于 heights.size() - 1 时，右边界高度记为 0，保证在遍历完成后栈也被清空，因为栈中不会有比 0 更矮的柱子。当计算左边界时，栈为空后左边界记为 -1，这样就可以在当栈底的柱子都比 i 对应的柱子高时，将栈底的柱子真包含（计算宽度时自动加1）。

class Solution
{
public:
    int largestRectangleArea(vector<int>& heights)
    {
        stack<int, vector<int>> st;
        int maxArea = 0;
        
        for (int i = 0; i <= heights.size(); ++i)
        {
            int rightHeight = i == heights.size() ? 0 : heights[i];
            while (!st.empty() && heights[st.top()] > rightHeight)
            {
                int height = heights[st.top()];
                st.pop();

                int left = st.empty() ? -1 : st.top();
                maxArea = max(maxArea, (i - left - 1) * height);
            }
			
            if(i < heights.size())
            {
            	st.push(i);
            }
        }
        
        return maxArea;
    }
};

3. 队列

队列（Queue）是限制仅允许在表的一端进行插入、在另一端进行删除的线性表。

允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。当表中不含任何元素时称为空队列。队列的修改遵从先进先出原则。

在 STL 中，队列对应 std::queue。std::queue 是一个容器适配器，默认底层容器为 std::deque，亦可通过模板参数指定指定具体容器。

1	template <class _Ty, class _Container = deque<_Ty>> class queue;

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

example

input：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
output：
[null, null, null, 1, 1, false]

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

该题目的关键在于理解数据同步的时机。将栈分为两个，一个用作输入，一个用作输出。输入栈 inStack 只承担 push 的职责，sync 负责将数据同步到 outStack，直到 inStack 被清空。

只有当 outStack 为空时才能进行数据同步。设想，如果 outStack 不为空，就将 inStack 的数据同步过来了，那么 inStack 同步过来的数据将在栈顶，这时候通过 outStack 取数据会先取出新加入的数据，违背了先进先出的原则。

class MyQueue
{
private:
    void sync()
    {
        while (!inStack.empty())
        {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue()
    {
    }

    void push(int x)
    {
        inStack.push(x);
    }

    int pop()
    {
        if (outStack.empty())
        {
            sync();
        }
        int rear = outStack.top();
        outStack.pop();
        return rear;
    }

    int peek()
    {
        if (outStack.empty())
        {
            sync();
        }
        return outStack.top();
    }

    bool empty()
    {
        return inStack.empty() && outStack.empty();
    }

    stack<int> inStack;
    stack<int> outStack;
};

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

example

input：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
output：
[null, null, null, 2, 2, false]

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

本题笔者最先想到的是一个非常规的解法。使用一个队列 topQueue 只存栈顶元素，这个 topQueue 只有两种状态，要么存在一个元素，要么为空。使用 dataQueue 存剩余元素。

使用一个 sync 方法，循环 dataQueue.size() - 1 次，每次将队头元素放到队尾。这样剩余的一个元素就是需要模拟的栈顶的元素。pop 和 top 时都只需要直接取 topQueue 的元素即可。如果为空的话 sync 一次就好。

值得注意的是 push 时，如果 topQueue 不为空，要先将里面的元素放入 dataQueue 的队尾，这样才能保持模拟栈后进先出的特性。设想，如果不放，那么下一次取 top 时将直接使用 topQueue 中缓存的元素，而不是新 push 的元素，这是错误的。

同时，因为 topQueue 永远只存一个元素或为空，所以完全没有使用队列的必要，用一个变量表示即可，用一个队列亦可模拟栈。

class MyStack
{
private:
    void sync()
    {
        int n = dataQueue.size();
        for (int i = 0; i < n - 1; ++i)
        {
            int frontVal = dataQueue.front();
            dataQueue.pop();
            dataQueue.push(frontVal);
        }

        topQueue.push(dataQueue.front());
        dataQueue.pop();
    }

public:
    MyStack()
    {
    }

    void push(int x)
    {
        if (!topQueue.empty())
        {
            dataQueue.push(topQueue.front());
            topQueue.pop();
        }
        dataQueue.push(x);
    }

    int pop()
    {
        if (topQueue.empty())
        {
            sync();
        }
        int topVal = topQueue.front();
        topQueue.pop();
        return topVal;
    }

    int top()
    {
        if (topQueue.empty())
        {
            sync();
        }

        return topQueue.front();
    }

    bool empty()
    {
        return dataQueue.empty() && topQueue.empty();
    }

    queue<int> dataQueue;
    queue<int> topQueue;
};

Zwei

数据结构与算法

1. 综述

1. 定义

2. 复杂度

3. 分类

2. 线性结构

1. 线性表

2.栈

3. 队列