Linear

自动关联目录:Linear

线性结构是元素排成一列的结构。区别在于允许在哪些位置插入/删除。

总览

结构插入/删除位置访问典型用途
数组任意(但要搬移)O(1)O(1) 随机默认选择
链表已知位置O(1)O(1)O(n)O(n) 查找频繁中间插入删除
栈只在顶端只看顶递归、括号匹配、单调栈
队列尾进头出只看头尾BFS、缓冲
双端队列两端只看两端滑动窗口、0-1 BFS
单调栈/队列受限 + 保序—优化 DP、求区间最值

最重要的原则:能用数组就用数组。数组缓存友好、实现简单、随机访问快,链表只在特定场景才划算。

数组 vs 链表

操作数组(动态)链表
随机访问O(1)O(1)O(n)O(n)
头部插入O(n)O(n)O(1)O(1)
尾部插入O(1)O(1) 均摊O(1)O(1)(有尾指针)
中间插入(已知位置)O(n)O(n)O(1)O(1)
内存开销无额外指针每节点多 1~2 个指针
缓存局部性极好差(指针跳转)

为什么数组通常更快:现代 CPU 有预取(prefetch)和缓存行(64 字节)。数组顺序访问时,一次加载能用到 8 个 int;链表每次访问都要一次可能的 cache miss(约 100 个周期的差距)。

经验值:即使理论上链表更优,元素数 <10410^4 时数组通常还是更快。

栈(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

为什么是O(n)O(n):每个元素入栈一次、出栈一次,总共2n2n 次操作。

为什么对:栈里维护"还没找到答案的元素的下标",且它们的值递减。新元素 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;
}

复杂度:O(n)O(n)(每个元素入队出队各一次),而不是暴力的O(nk)O(nk)。

为什么队首是最大值:队列维护递减,队首最大;同时队首下标最老,会最先过期。

注意第 2 步用 <= 还是 <:影响相等元素的处理。用 <= 会保留新元素(更晚过期),通常更好。

单调队列优化 DP

形如:

dp[i]=max⁡j∈[i−k, i−1](dp[j]+f(i))dp[i] = \max_{j \in [i-k,\, i-1]} \big(dp[j] + f(i)\big)

用单调队列维护候选 dp[j] 的最大值,把O(nk)O(nk) 优化到O(n)O(n)。

// 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。

单调性的本质

单调栈和单调队列都在利用同一个思想:

如果元素xx 比yy 早出现且x≤yx \le y,那么xx 永远不会成为答案(yy 活得更久且更大)→ 可以永久淘汰xx。

这叫支配关系。一旦识别出"某个元素被另一个完全支配",就可以用单调结构O(n)O(n) 扫一遍。

其他线性技巧

双指针

// 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 入队