Linear
自动关联目录:Linear
线性结构是元素排成一列的结构。区别在于允许在哪些位置插入/删除。
总览
| 结构 | 插入/删除位置 | 访问 | 典型用途 |
|---|---|---|---|
| 数组 | 任意(但要搬移) | 随机 | 默认选择 |
| 链表 | 已知位置 | 查找 | 频繁中间插入删除 |
| 栈 | 只在顶端 | 只看顶 | 递归、括号匹配、单调栈 |
| 队列 | 尾进头出 | 只看头尾 | BFS、缓冲 |
| 双端队列 | 两端 | 只看两端 | 滑动窗口、0-1 BFS |
| 单调栈/队列 | 受限 + 保序 | — | 优化 DP、求区间最值 |
最重要的原则:能用数组就用数组。数组缓存友好、实现简单、随机访问快,链表只在特定场景才划算。
数组 vs 链表
| 操作 | 数组(动态) | 链表 |
|---|---|---|
| 随机访问 | ||
| 头部插入 | ||
| 尾部插入 | 均摊 | (有尾指针) |
| 中间插入(已知位置) | ||
| 内存开销 | 无额外指针 | 每节点多 1~2 个指针 |
| 缓存局部性 | 极好 | 差(指针跳转) |
为什么数组通常更快:现代 CPU 有预取(prefetch)和缓存行(64 字节)。数组顺序访问时,一次加载能用到 8 个 int;链表每次访问都要一次可能的 cache miss(约 100 个周期的差距)。
经验值:即使理论上链表更优,元素数 < 时数组通常还是更快。
栈(Stack)
LIFO:后进先出。
stack<int> st;
st.push(1); st.push(2);
int t = st.top(); // 2
st.pop();应用:
- 递归的函数调用栈
- 括号匹配
- 表达式求值(中缀转后缀)
- DFS 的显式实现
- 单调栈
括号匹配
bool valid(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else {
if (st.empty()) return false;
char t = st.top(); st.pop();
if ((c == ')' && t != '(') || (c == ']' && t != '[') || (c == '}' && t != '{'))
return false;
}
}
return st.empty();
}队列(Queue)
FIFO:先进先出。
queue<int> q;
q.push(1); q.push(2);
int f = q.front(); // 1
q.pop();循环队列:普通数组队列出队会浪费前面的空间,用取模把它绕回来。
int q[N], head = 0, tail = 0;
void push(int x) { q[tail++] = x; if (tail == N) tail = 0; }
int pop() { int x = q[head++]; if (head == N) head = 0; return x; }
bool empty() { return head == tail; }应用:BFS、缓冲区、生产者-消费者。
双端队列(Deque)
两端都能进出。
deque<int> dq;
dq.push_back(1); dq.push_front(2);
dq.pop_front(); dq.pop_back();应用:
- 滑动窗口最大值(单调队列)
- 0-1 BFS
- 需要同时看两端的场景
单调栈
栈内元素保持单调(递增或递减)。用来求"左边/右边第一个比它大/小的元素"。
求"右边第一个更大元素"(Next Greater Element)
// 单调递减栈(栈底到栈顶递减)
vector<int> nge(n, -1);
stack<int> st; // 存下标
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
nge[st.top()] = i; // 找到了!a[i] 是 st.top() 右边第一个更大的
st.pop();
}
st.push(i);
}
// 栈里剩下的元素右边没有更大的,保持 -1为什么是:每个元素入栈一次、出栈一次,总共 次操作。
为什么对:栈里维护"还没找到答案的元素的下标",且它们的值递减。新元素 a[i] 来了,所有比它小的栈顶元素都找到了答案(就是 i),弹出。
变体
| 求什么 | 栈的单调性 | 比较符号 |
|---|---|---|
| 右边第一个 更大 | 递减 | a[top] < a[i] 时弹出 |
| 右边第一个 更小 | 递增 | a[top] > a[i] 时弹出 |
| 左边第一个更大 | 递减 | 从右往左扫 |
| 左边第一个更小 | 递增 | 从右往左扫 |
典型应用
接雨水
// 单调栈解法:栈递减,遇到更高的就形成凹槽
long long trap(vector<int>& h) {
stack<int> st;
long long ans = 0;
for (int i = 0; i < (int)h.size(); i++) {
while (!st.empty() && h[i] > h[st.top()]) {
int bottom = st.top(); st.pop();
if (st.empty()) break; // 左边没有更高的墙
int width = i - st.top() - 1;
int height = min(h[i], h[st.top()]) - h[bottom];
ans += 1LL * width * height;
}
st.push(i);
}
return ans;
}柱状图最大矩形
栈递增,遇到更矮的就弹出并计算以它为高的最大矩形。
单调队列
队列内元素保持单调,且有过期机制(下标超出窗口就出队)。
滑动窗口最大值
数组
a,窗口大小k,求每个窗口的最大值。
vector<int> maxSlidingWindow(vector<int>& a, int k) {
deque<int> dq; // 存下标,保证对应的值递减
vector<int> ans;
for (int i = 0; i < (int)a.size(); i++) {
// 1. 过期:队首下标 < i-k+1 就出队
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
// 2. 维护单调递减:队尾比新元素小的都出队
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
// 3. 入队
dq.push_back(i);
// 4. 窗口形成后记录答案(队首就是最大值)
if (i >= k - 1) ans.push_back(a[dq.front()]);
}
return ans;
}复杂度:(每个元素入队出队各一次),而不是暴力的。
为什么队首是最大值:队列维护递减,队首最大;同时队首下标最老,会最先过期。
注意第 2 步用 <= 还是 <:影响相等元素的处理。用 <= 会保留新元素(更晚过期),通常更好。
单调队列优化 DP
形如:
用单调队列维护候选 dp[j] 的最大值,把 优化到。
// dp[i] = max_{j in [i-k, i-1]} dp[j] + a[i]
deque<int> dq;
for (int i = 1; i <= n; i++) {
while (!dq.empty() && dq.front() < i - k) dq.pop_front(); // 过期
if (i > 1) {
while (!dq.empty() && dp[dq.back()] <= dp[i-1]) dq.pop_back();
dq.push_back(i - 1);
}
dp[i] = (dq.empty() ? 0 : dp[dq.front()]) + a[i];
}识别信号:转移是一个滑动窗口的 max/min。
单调性的本质
单调栈和单调队列都在利用同一个思想:
如果元素 比 早出现且,那么 永远不会成为答案( 活得更久且更大)→ 可以永久淘汰。
这叫支配关系。一旦识别出"某个元素被另一个完全支配",就可以用单调结构 扫一遍。
其他线性技巧
双指针
// 1. 同向(快慢指针):链表判环、去重、滑动窗口
int slow = 0;
for (int fast = 0; fast < n; fast++) {
if (/* 条件 */) a[slow++] = a[fast];
}
// 2. 相向(左右指针):有序数组两数之和
int l = 0, r = n - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) { /* 找到 */ break; }
else if (s < target) l++;
else r--;
}相向双指针为什么对:a[l] + a[r] 太小 → 增大只能右移 l(因为 r 已经最大);太大 → 左移 r。每一步都排除一行/一列。
前缀和数组
见前缀和章节。
差分数组
见前缀和章节。
常见坑
stack::top()前没检查empty():UB(可能崩溃)- 单调栈的比较符号写反:求"更大"却写成递增栈
- 单调队列忘了处理过期:窗口滑过去了,旧元素还在队首
- 队列用数组实现时没取模:越界或浪费空间
- 单调栈存的是下标还是值:通常存下标(能算距离、能判过期)
deque的性能:std::deque是分段连续,比vector慢。滑动窗口用数组模拟的双端队列更快- 滑动窗口的窗口大小边界:
i >= k-1才开始记录答案 - 单调队列优化 DP 时
dp[i-1]入队的时机:要在算dp[i]之前把i-1入队