题目分析

本题要求用最少的区间加 $1$ 操作，将初始全 $0$ 的序列变为目标高度序列 $h_1, h_2, \dots, h_n$。

问题抽象

给定初始全零数组 $A = [0, 0, \dots, 0]$，要通过最少的“区间 $+1$”操作，得到目标数组 $H = [h_1, h_2, \dots, h_n]$。

关键思路与贪心策略

考虑相邻两块积木的高度差：

• 如果 $h_i > h_{i-1}$，说明在第 $i$ 块积木上需要比前一块多增加 $h_i - h_{i-1}$ 次操作
• 如果 $h_i \leq h_{i-1}$，说明这部分操作可以被前面的区间操作覆盖

核心公式： 设 $h_0 = 0$，则最少操作次数为：

算法正确性证明

从构造角度理解：

• 第一次操作区间 $[1, n]$，将所有积木高度 $+1$
• 对于每个 $i$，如果 $h_i > h_{i-1}$，需要额外进行 $h_i - h_{i-1}$ 次以 $i$ 为起点的区间操作
• 这样保证每块积木达到目标高度，且操作次数最少

从差分角度理解：

• 设差分数组 $d_i = h_i - h_{i-1}$（其中 $h_0 = 0$）
• 每次区间 $[L, R]$ 加 $1$ 相当于 $d_L$ 加 $1$，$d_{R+1}$ 减 $1$
• 最终 $d_1 = h_1$，$d_i = h_i - h_{i-1}$（$i \geq 2$）
• 最少操作次数等于所有正差分之和

代码解析

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >

int const N = 1e5 + 10;
int h[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 读入目标高度序列
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    
    int ans = 0;
    
    // 计算所有正差分之和
    for (int i = 1; i <= n; i++)
        if (h[i - 1] < h[i])
            ans += h[i] - h[i - 1];
    
    cout << ans;
    return 0;
}

代码逻辑：

1. 读入 $n$ 和目标高度数组 $h$
2. 初始化 $ans = 0$
3. 遍历 $i$ 从 $1$ 到 $n$：
   • 如果 $h_i > h_{i-1}$，将差值加入答案
   • 隐含 $h_0 = 0$ 的处理
4. 输出结果

复杂度分析

• 时间复杂度：$O(n)$
  只需一次线性扫描
• 空间复杂度：$O(n)$
  存储高度数组

示例验证

样例输入：

n = 5
h = [2, 3, 4, 1, 2]

计算过程：

• $i=1$：$h_1 - h_0 = 2 - 0 = 2$，$ans = 2$
• $i=2$：$h_2 - h_1 = 3 - 2 = 1$，$ans = 3$
• $i=3$：$h_3 - h_2 = 4 - 3 = 1$，$ans = 4$
• $i=4$：$h_4 - h_3 = 1 - 4 = -3$（不增加）
• $i=5$：$h_5 - h_4 = 2 - 1 = 1$，$ans = 5$

输出：5，与样例一致。

算法优势

• 高效简洁：$O(n)$ 时间复杂度，$O(n)$ 空间复杂度
• 易于实现：核心代码仅需几行
• 正确性保证：基于差分数组的严格数学推导

该解法充分利用了问题的特殊结构，通过分析相邻块的高度关系，避免了复杂的模拟过程，是本题的最优解法。