第二题时空复杂度详解

第二题：最小化最大值之和 - 时空复杂度详解

题目回顾

问题：将数组分成若干段，每段的和 ≤ m，最小化所有段的最大值之和。

DP 状态转移方程：

dp[i] = min_{0 ≤ j < i} { dp[j] + max(h[j+1], h[j+2], ..., h[i]) }
约束条件：sum(h[j+1]...h[i]) ≤ m

---

版本1：朴素DP（O(n²) 版本）

代码核心逻辑（第202-210行）

for (int i = 1; i <= n; ++i) {
    ll local_max = 0;
    ll seg_sum = 0;
    for (int j = i - 1; j >= 0; --j) {
        seg_sum += h[j + 1];
        if (seg_sum > m) break;  // 剪枝：和超过 m 就停止
        local_max = max(local_max, h[j + 1]);
        dp[i] = min(dp[i], dp[j] + local_max);
    }
}

时间复杂度分析：O(n²)

外层循环

• 循环次数：i 从 1 到 n，共 n 次

内层循环（对于每个 i）

• 循环次数：j 从 i-1 倒序遍历到 0，最坏情况下需要遍历 i 次
• 每次循环的操作：
  • seg_sum += h[j + 1]：O(1)
  • if (seg_sum > m) break：O(1)（剪枝优化）
  • local_max = max(local_max, h[j + 1])：O(1)
  • dp[i] = min(dp[i], dp[j] + local_max)：O(1)

总时间复杂度计算

最坏情况（没有剪枝生效）：

• i = 1：内层循环 1 次
• i = 2：内层循环 2 次
• i = 3：内层循环 3 次
• …
• i = n：内层循环 n 次

总操作次数 = 1 + 2 + 3 + … + n = n(n+1)/2 = O(n²)

结论：时间复杂度为 O(n²)

空间复杂度分析：O(n)

• dp 数组：O(n)
• h 数组：O(n)
• local_max、seg_sum 等临时变量：O(1)
• 总空间复杂度：O(n)

---

版本2：单调栈+线段树优化（O(n log n) 版本）

核心思想

1. 单调栈：维护当前区间内 h 值的递减序列，快速确定每个位置作为最大值控制的区间范围
2. 线段树：维护 dp[j] + max(h[j+1]...h[i]) 的最小值，支持区间修改和区间查询

代码核心逻辑（第339-371行）

for (int i = 1; i <= n; i++) {
    // 1. 维护区间和限制
    current_sum += h[i];
    while (current_sum > m) {
        current_sum -= h[left + 1];
        left++;
    }
 
    // 2. 单调栈维护区间最大值贡献
    while (!stk.empty() && h[stk.top()] <= h[i]) {
        int idx = stk.top();
        stk.pop();
        int l_bound = stk.empty() ? 0 : stk.top();
        update_add(1, l_bound, idx - 1, h[i] - h[idx]);
    }
    stk.push(i);
 
    // 3. 添加新的决策点
    update_set(1, i - 1, dp[i - 1] + h[i]);
 
    // 4. 查询最优解
    dp[i] = query(1, left, i - 1);
}

时间复杂度分析：O(n log n)

1. 外层循环：O(n)

• 循环 n 次，i 从 1 到 n

2. 维护区间和限制（第341-345行）：均摊 O(1)

current_sum += h[i];  // O(1)
while (current_sum > m) {
    current_sum -= h[left + 1];  // O(1)
    left++;  // O(1)
}

分析：

• left 指针单调递增，每个元素最多被访问一次
• 虽然 while 循环可能执行多次，但总共只会执行 n 次（每个元素最多被减去一次）
• 均摊时间复杂度：O(1)

3. 单调栈维护（第347-361行）：均摊 O(log n)

while (!stk.empty() && h[stk.top()] <= h[i]) {
    int idx = stk.top();
    stk.pop();  // O(1)
    int l_bound = stk.empty() ? 0 : stk.top();
    update_add(1, l_bound, idx - 1, h[i] - h[idx]);  // O(log n)
}
stk.push(i);  // O(1)

分析：

• 单调栈操作：每个元素最多入栈一次、出栈一次，均摊 O(1)
• 线段树区间更新：update_add 的时间复杂度为 O(log n)
• 关键点：虽然 while 循环可能执行多次，但每个元素最多出栈一次
• 假设 while 循环总共执行 k 次，则总复杂度为 k × O(log n)
• 由于 k ≤ n（每个元素最多出栈一次），均摊时间复杂度：O(log n)

详细说明：

• 最坏情况：h 数组单调递增，每个元素入栈后立即被弹出，共 n 次出栈
• 每次出栈伴随一次 O(log n) 的线段树更新
• 总复杂度：n × O(log n) = O(n log n)，均摊到 n 次外层循环，每次 O(log n)

4. 添加新决策点（第367行）：O(log n)

update_set(1, i - 1, dp[i - 1] + h[i]);

• 线段树单点更新：O(log n)

5. 查询最优解（第371行）：O(log n)

dp[i] = query(1, left, i - 1);

• 线段树区间查询：O(log n)

总时间复杂度

每次外层循环：

• 维护区间和：O(1)
• 单调栈维护：O(log n)（均摊）
• 添加决策点：O(log n)
• 查询最优解：O(log n)

总时间复杂度：n × (O(1) + O(log n) + O(log n) + O(log n)) = O(n log n)

空间复杂度分析：O(n)

1. 线段树：O(n)

struct SegmentTree {
    int l, r;
    ll min_val;
    ll lazy;
} tree[MAXN * 4];

• 线段树使用 4 倍空间：O(4n) = O(n)

2. DP 数组：O(n)

ll dp[MAXN];

3. 输入数组：O(n)

int h[MAXN];

4. 单调栈：O(n)

stack<int> stk;

• 最坏情况（h 单调递减）：栈中存储所有元素，O(n)

5. 其他变量：O(1)

• current_sum、left、i 等

总空间复杂度：O(n) + O(n) + O(n) + O(n) = O(n)

---

复杂度对比总结

版本	时间复杂度	空间复杂度	适用场景
版本1（朴素DP）	O(n²)	O(n)	n ≤ 10³，数据范围较小
版本2（单调栈+线段树）	O(n log n)	O(n)	n ≤ 10⁵，需要高效算法

---

为什么版本2能优化到 O(n log n)？

关键优化点

1. 单调栈优化：

   • 朴素方法需要 O(n) 时间计算每个区间的最大值
   • 单调栈通过维护递减序列，均摊 O(1) 时间确定最大值控制范围

2. 线段树优化：

   • 朴素方法需要 O(n) 时间枚举所有转移点并取最小值
   • 线段树在 O(log n) 时间内完成区间查询和区间修改

3. 区间和限制优化：

   • 使用双指针（left）维护滑动窗口，均摊 O(1) 时间

复杂度降低的数学证明

朴素DP：

• 对于每个 i，需要枚举所有可能的 j（最多 i 个）
• 总操作数：1 + 2 + … + n = O(n²)

优化版本：

• 对于每个 i，单调栈操作均摊 O(1)，线段树操作 O(log n)
• 总操作数：n × O(log n) = O(n log n)

优化效果：从 O(n²) 降低到 O(n log n)，当 n = 10⁵ 时，从 10¹⁰ 次操作降低到约 10⁶ 次操作，提升约 10⁴ 倍。

---

实际运行时间估算

假设单次操作耗时 1ns：

n	版本1（O(n²)）	版本2（O(n log n)）
10³	1ms	0.01ms
10⁴	100ms	0.13ms
10⁵	10s	1.7ms

可以看出，当 n 较大时，优化版本的性能提升非常显著。