LeetCode 题解Minimum Number of Increments on Subarrays to Form a Target Array——从分治模拟到线段树再到单趟贪心的三阶演进【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文基于本仓库的 articles/minimum-number-of-increments-on-subarrays-to-form-a-target-array.md 展开系统讲解 LeetCode 经典问题Minimum Number of Increments on Subarrays to Form a Target Array将全零数组通过每次对连续子数组 1的操作用最少次数构造成目标数组。文章完整覆盖三种解法O(n²) 的分治模拟、O(n log n) 的线段树优化以及 O(n) 的单趟贪心并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整实现与复杂度分析。读完本文你将掌握按层涂色的分治思想、用线段树把区间最小值查询降到 O(log n) 的技巧以及只数上升沿这一贪心模式的推导过程能够从容应对同类区间增量构造问题。前置知识Prerequisites在尝试解决本题之前建议先熟悉以下四块基础能力它们分别对应三种解法的底层支撑分治Divide and Conquer——在关键点例如最小值所在位置处把问题拆分成相互独立的子问题是解法一的骨架线段树Segment Tree——支持高效的区间最小值查询用于把解法一中的线性扫描替换为对数级查询从而优化整体复杂度是解法二的核心数据结构贪心算法Greedy——识别出统计上升段就能直接得到最优答案是解法三的洞察来源数组遍历Array Traversal——单趟处理相邻元素的差值是贪心解法的落地手段。需要说明的是本仓库是一个多语言 LeetCode 题解仓库详见 README.md上述前置知识点中分治 最小值切分的思路在仓库的 maximum-subarray.md、merge-intervals.md 等区间类文章中有大量呼应而根据相邻元素差值决定是否新增操作的贪心模式与 trapping-rain-water.md 这类按高度/层数思考的题目思路一致可以互相印证。问题建模把数组看作一层一层的横条纹在进入三种解法之前先建立一个贯穿全文的直觉模型把 target 数组想象成一幅由水平条纹堆叠出来的柱状图。每次操作把某个连续子数组整体 1等价于在该子数组覆盖的柱子上多涂一层横条纹。目标是用最少的涂层次数把高度从 0 堆叠成 target 所描述的轮廓。这个模型直接导出了解法一的分治视角某个区间内的最小值就是该区间的地板地板以下的层数必须先一次性涂满然后再分别在最小值的左右两侧独立地往上继续涂。三种解法的共同点是都在回答同一个问题每一层横条纹最多能连续覆盖多长差别只在于统计方式——是递归找最小值分治、用数据结构加速找最小值线段树还是直接数上升沿贪心。解法一分治模拟Simulation直觉把构建 target 数组的过程想象成按水平层涂色。每次操作对连续子数组 1就像涂一层颜色。递归地执行在当前区间[l, r]内找到最小值把从当前高度到该最小值的所有层一次性涂满需要min_value - current_height次操作最小值把区间切分成左右两个互不相干的部分分别递归处理。关键点在于最小值充当了地板它把问题隔离成两个独立的子问题——左侧和右侧的柱子永远不会共享同一笔跨过最小值的涂层因此可以分开独立求解。算法步骤定义递归函数参数为左边界l、右边界r、当前已涂高度h递归出口若l r返回0在区间内线性扫描找到最小值所在下标minIdx把target[minIdx] - h累加到结果即到达该最小值所需新增的层数以target[minIdx]作为新的高度递归求解左半部分[l, minIdx - 1]与右半部分[minIdx 1, r]返回三部分之和。代码实现Pythonclass Solution: def minNumberOperations(self, target: List[int]) - int: def rec(l, r, h): if l r: return 0 minIdx l for i in range(l 1, r 1): if target[i] target[minIdx]: minIdx i res target[minIdx] - h return res rec(l, minIdx - 1, target[minIdx]) rec(minIdx 1, r, target[minIdx]) return rec(0, len(target) - 1, 0)Javapublic class Solution { public int minNumberOperations(int[] target) { return rec(target, 0, target.length - 1, 0); } private int rec(int[] target, int l, int r, int h) { if (l r) return 0; int minIdx l; for (int i l 1; i r; i) { if (target[i] target[minIdx]) { minIdx i; } } int res target[minIdx] - h; res rec(target, l, minIdx - 1, target[minIdx]); res rec(target, minIdx 1, r, target[minIdx]); return res; } }Cclass Solution { public: int minNumberOperations(vectorint target) { return rec(target, 0, target.size() - 1, 0); } private: int rec(vectorint target, int l, int r, int h) { if (l r) return 0; int minIdx l; for (int i l 1; i r; i) { if (target[i] target[minIdx]) { minIdx i; } } int res target[minIdx] - h; res rec(target, l, minIdx - 1, target[minIdx]); res rec(target, minIdx 1, r, target[minIdx]); return res; } };JavaScriptclass Solution { /** * param {number[]} target * return {number} */ minNumberOperations(target) { const rec (l, r, h) { if (l r) return 0; let minIdx l; for (let i l 1; i r; i) { if (target[i] target[minIdx]) { minIdx i; } } let res target[minIdx] - h; res rec(l, minIdx - 1, target[minIdx]); res rec(minIdx 1, r, target[minIdx]); return res; }; return rec(0, target.length - 1, 0); } }C#public class Solution { public int MinNumberOperations(int[] target) { return Rec(target, 0, target.Length - 1, 0); } private int Rec(int[] target, int l, int r, int h) { if (l r) return 0; int minIdx l; for (int i l 1; i r; i) { if (target[i] target[minIdx]) { minIdx i; } } int res target[minIdx] - h; res Rec(target, l, minIdx - 1, target[minIdx]); res Rec(target, minIdx 1, r, target[minIdx]); return res; } }Gofunc minNumberOperations(target []int) int { var rec func(l, r, h int) int rec func(l, r, h int) int { if l r { return 0 } minIdx : l for i : l 1; i r; i { if target[i] target[minIdx] { minIdx i } } res : target[minIdx] - h res rec(l, minIdx-1, target[minIdx]) res rec(minIdx1, r, target[minIdx]) return res } return rec(0, len(target)-1, 0) }Kotlinclass Solution { fun minNumberOperations(target: IntArray): Int { fun rec(l: Int, r: Int, h: Int): Int { if (l r) return 0 var minIdx l for (i in l 1..r) { if (target[i] target[minIdx]) { minIdx i } } var res target[minIdx] - h res rec(l, minIdx - 1, target[minIdx]) res rec(minIdx 1, r, target[minIdx]) return res } return rec(0, target.size - 1, 0) } }Swiftclass Solution { func minNumberOperations(_ target: [Int]) - Int { func rec(_ l: Int, _ r: Int, _ h: Int) - Int { if l r { return 0 } var minIdx l for i in (l 1)...r { if target[i] target[minIdx] { minIdx i } } var res target[minIdx] - h res rec(l, minIdx - 1, target[minIdx]) res rec(minIdx 1, r, target[minIdx]) return res } return rec(0, target.count - 1, 0) } }Rustimpl Solution { pub fn min_number_operations(target: Veci32) - i32 { fn rec(target: [i32], l: i32, r: i32, h: i32) - i32 { if l r { return 0; } let (l, r) (l as usize, r as usize); let mut min_idx l; for i in l 1..r { if target[i] target[min_idx] { min_idx i; } } let res target[min_idx] - h; res rec(target, l as i32, min_idx as i32 - 1, target[min_idx]) rec(target, min_idx as i32 1, r as i32, target[min_idx]) } rec(target, 0, target.len() as i32 - 1, 0) } }时间复杂度与空间复杂度时间复杂度O(n²)——最坏情况如单调递减数组下每次递归都要线性扫描整个区间找最小值空间复杂度O(n)——递归栈深度在最坏情况下为 O(n)例如最小值总在端点退化为链式递归。解法二线段树优化Segment Tree直觉解法一之所以慢是因为每次在区间内找最小值都要 O(n) 线性扫描。线段树可以把区间最小值查询压缩到 O(log n)整体分治逻辑完全不变仍然在最小值处切分只不过把扫描找最小替换成查线段树。这样一来总时间复杂度从 O(n²) 降为 O(n log n)。算法步骤构建一棵线段树树的每个节点存储对应区间内最小值所在的下标注意存下标而非值因为后续递归需要按位置切分沿用同样的递归分治流程查询线段树得到当前区间[l, r]内最小值下标minIdx把target[minIdx] - h最小值与当前高度之差累加到结果递归处理左子区间[l, minIdx - 1]与右子区间[minIdx 1, r]返回累计的操作总数。实现细节上所有语言都采用了把数组长度补齐到 2 的幂的技巧多出的位置填充无穷大INF这样线段树可以被组织成满二叉树直接用2 * n大小的数组存储父子节点通过j 1与(j 1) | 1访问。Python 版的SegmentTree还额外提供了update方法单点更新后沿路径向上重算说明该类是一个可复用的通用最小值下标线段树不只是为本题定制。代码实现PythonINF float(inf) class SegmentTree: def __init__(self, A): self.A A[:] self.n len(A) while (self.n (self.n - 1)) ! 0: self.A.append(INF) self.n 1 self.tree [0] * (2 * self.n) self.build() def build(self): for i in range(self.n): self.tree[self.n i] i for j in range(self.n - 1, 0, -1): a self.tree[j 1] b self.tree[(j 1) | 1] self.tree[j] a if self.A[a] self.A[b] else b def update(self, i, val): self.A[i] val j (self.n i) 1 while j 1: a self.tree[j 1] b self.tree[(j 1) | 1] self.tree[j] a if self.A[a] self.A[b] else b j 1 def query(self, ql, qh): return self._query(1, 0, self.n - 1, ql, qh) def _query(self, node, l, h, ql, qh): if ql h or qh l: return -1 if l ql and h qh: return self.tree[node] mid (l h) 1 a self._query(node 1, l, mid, ql, qh) b self._query((node 1) | 1, mid 1, h, ql, qh) if a -1: return b if b -1: return a return a if self.A[a] self.A[b] else b class Solution: def minNumberOperations(self, target: List[int]) - int: seg SegmentTree(target) stack [(0, len(target) - 1, 0)] res 0 while stack: l, r, h stack.pop() if l r: continue minIdx seg.query(l, r) res target[minIdx] - h stack.append((l, minIdx - 1, target[minIdx])) stack.append((minIdx 1, r, target[minIdx])) return res说明Python 版将递归改写为显式栈效果等价于解法一的递归流程同时避免了 Python 默认递归深度限制带来的风险其余语言版本保留了递归写法。Javaclass SegmentTree { int[] A; int[] tree; int n; final int INF Integer.MAX_VALUE; SegmentTree(int[] arr) { int len arr.length; int pow2 1; while (pow2 len) pow2 1; n pow2; A new int[n]; System.arraycopy(arr, 0, A, 0, arr.length); for (int i arr.length; i n; i) A[i] INF; tree new int[2 * n]; build(); } void build() { for (int i 0; i n; i) { tree[n i] i; } for (int i n - 1; i 0; i--) { int a tree[i 1], b tree[(i 1) | 1]; tree[i] A[a] A[b] ? a : b; } } int query(int ql, int qh) { return _query(1, 0, n - 1, ql, qh); } int _query(int node, int l, int h, int ql, int qh) { if (ql h || qh l) return -1; if (ql l h qh) return tree[node]; int mid (l h) 1; int left _query(node 1, l, mid, ql, qh); int right _query((node 1) | 1, mid 1, h, ql, qh); if (left -1) return right; if (right -1) return left; return A[left] A[right] ? left : right; } } public class Solution { public int minNumberOperations(int[] target) { SegmentTree seg new SegmentTree(target); return rec(0, target.length - 1, 0, target, seg); } private int rec(int l, int r, int h, int[] target, SegmentTree seg) { if (l r) return 0; int minIdx seg.query(l, r); int res target[minIdx] - h; res rec(l, minIdx - 1, target[minIdx], target, seg); res rec(minIdx 1, r, target[minIdx], target, seg); return res; } }Cclass SegmentTree { public: int n; vectorint A, tree; const int INF INT_MAX; SegmentTree(vectorint arr) { A arr; n arr.size(); while (__builtin_popcount(n) ! 1) { A.push_back(INF); n; } tree.resize(2 * n); build(); } void build() { for (int i 0; i n; i) { tree[n i] i; } for (int j n - 1; j 1; --j) { int a tree[j 1], b tree[(j 1) | 1]; tree[j] A[a] A[b] ? a : b; } } int query(int ql, int qh) { return _query(1, 0, n - 1, ql, qh); } int _query(int node, int l, int h, int ql, int qh) { if (ql h || qh l) return -1; if (l ql h qh) return tree[node]; int mid (l h) 1; int a _query(node 1, l, mid, ql, qh); int b _query((node 1) | 1, mid 1, h, ql, qh); if (a -1) return b; if (b -1) return a; return A[a] A[b] ? a : b; } }; class Solution { public: int minNumberOperations(vectorint target) { SegmentTree seg(target); return rec(0, target.size() - 1, 0, target, seg); } int rec(int l, int r, int h, vectorint target, SegmentTree seg) { if (l r) return 0; int minIdx seg.query(l, r); int res target[minIdx] - h; res rec(l, minIdx - 1, target[minIdx], target, seg); res rec(minIdx 1, r, target[minIdx], target, seg); return res; } };JavaScriptclass SegmentTree { constructor(A) { this.A [...A]; this.n A.length; this.INF Number.POSITIVE_INFINITY; while ((this.n (this.n - 1)) ! 0) { this.A.push(this.INF); this.n; } this.tree Array(2 * this.n).fill(0); this.build(); } build() { for (let i 0; i this.n; i) { this.tree[this.n i] i; } for (let j this.n - 1; j 1; j--) { let a this.tree[j 1]; let b this.tree[(j 1) | 1]; this.tree[j] this.A[a] this.A[b] ? a : b; } } update(i, val) { this.A[i] val; let j (this.n i) 1; while (j 1) { let a this.tree[j 1]; let b this.tree[(j 1) | 1]; this.tree[j] this.A[a] this.A[b] ? a : b; j 1; } } query(ql, qh) { return this._query(1, 0, this.n - 1, ql, qh); } _query(node, l, h, ql, qh) { if (ql h || qh l) return -1; if (l ql h qh) return this.tree[node]; let mid (l h) 1; let a this._query(node 1, l, mid, ql, qh); let b this._query((node 1) | 1, mid 1, h, ql, qh); if (a -1) return b; if (b -1) return a; return this.A[a] this.A[b] ? a : b; } } class Solution { /** * param {number[]} target * return {number} */ minNumberOperations(target) { const seg new SegmentTree(target); const rec (l, r, h) { if (l r) return 0; const minIdx seg.query(l, r); let res target[minIdx] - h; res rec(l, minIdx - 1, target[minIdx]); res rec(minIdx 1, r, target[minIdx]); return res; }; return rec(0, target.length - 1, 0); } }C#public class SegmentTree { private int[] A; private int[] tree; private int n; private const int INF int.MaxValue; public SegmentTree(int[] arr) { int len arr.Length; int pow2 1; while (pow2 len) pow2 1; n pow2; A new int[n]; Array.Copy(arr, A, arr.Length); for (int i arr.Length; i n; i) A[i] INF; tree new int[2 * n]; Build(); } private void Build() { for (int i 0; i n; i) { tree[n i] i; } for (int i n - 1; i 0; i--) { int a tree[i 1]; int b tree[(i 1) | 1]; tree[i] A[a] A[b] ? a : b; } } public int Query(int ql, int qh) { return Query(1, 0, n - 1, ql, qh); } private int Query(int node, int l, int h, int ql, int qh) { if (ql h || qh l) return -1; if (ql l h qh) return tree[node]; int mid (l h) 1; int left Query(node 1, l, mid, ql, qh); int right Query((node 1) | 1, mid 1, h, ql, qh); if (left -1) return right; if (right -1) return left; return A[left] A[right] ? left : right; } } public class Solution { public int MinNumberOperations(int[] target) { var seg new SegmentTree(target); return Rec(0, target.Length - 1, 0, target, seg); } private int Rec(int l, int r, int h, int[] target, SegmentTree seg) { if (l r) return 0; int minIdx seg.Query(l, r); int res target[minIdx] - h; res Rec(l, minIdx - 1, target[minIdx], target, seg); res Rec(minIdx 1, r, target[minIdx], target, seg); return res; } }Goconst INF int(^uint(0) 1) type SegmentTree struct { A []int tree []int n int } func NewSegmentTree(arr []int) *SegmentTree { n : len(arr) pow2 : 1 for pow2 n { pow2 1 } A : make([]int, pow2) copy(A, arr) for i : len(arr); i pow2; i { A[i] INF } tree : make([]int, 2*pow2) st : SegmentTree{A: A, tree: tree, n: pow2} st.build() return st } func (st *SegmentTree) build() { for i : 0; i st.n; i { st.tree[st.ni] i } for i : st.n - 1; i 0; i-- { a : st.tree[i1] b : st.tree[(i1)|1] if st.A[a] st.A[b] { st.tree[i] a } else { st.tree[i] b } } } func (st *SegmentTree) Query(ql, qh int) int { return st.query(1, 0, st.n-1, ql, qh) } func (st *SegmentTree) query(node, l, h, ql, qh int) int { if ql h || qh l { return -1 } if l ql h qh { return st.tree[node] } mid : (l h) 1 a : st.query(node1, l, mid, ql, qh) b : st.query((node1)|1, mid1, h, ql, qh) if a -1 { return b } if b -1 { return a } if st.A[a] st.A[b] { return a } return b } func minNumberOperations(target []int) int { seg : NewSegmentTree(target) var rec func(l, r, h int) int rec func(l, r, h int) int { if l r { return 0 } minIdx : seg.Query(l, r) res : target[minIdx] - h res rec(l, minIdx-1, target[minIdx]) res rec(minIdx1, r, target[minIdx]) return res } return rec(0, len(target)-1, 0) }Kotlinclass SegmentTree(arr: IntArray) { private val A: IntArray private val tree: IntArray private val n: Int init { var pow2 1 while (pow2 arr.size) pow2 pow2 shl 1 n pow2 A IntArray(n) { Int.MAX_VALUE } arr.copyInto(A) tree IntArray(2 * n) build() } private fun build() { for (i in 0 until n) { tree[n i] i } for (i in n - 1 downTo 1) { val a tree[i shl 1] val b tree[(i shl 1) or 1] tree[i] if (A[a] A[b]) a else b } } fun query(ql: Int, qh: Int): Int { return query(1, 0, n - 1, ql, qh) } private fun query(node: Int, l: Int, h: Int, ql: Int, qh: Int): Int { if (ql h || qh l) return -1 if (l ql h qh) return tree[node] val mid (l h) shr 1 val a query(node shl 1, l, mid, ql, qh) val b query((node shl 1) or 1, mid 1, h, ql, qh) if (a -1) return b if (b -1) return a return if (A[a] A[b]) a else b } } class Solution { fun minNumberOperations(target: IntArray): Int { val seg SegmentTree(target) fun rec(l: Int, r: Int, h: Int): Int { if (l r) return 0 val minIdx seg.query(l, r) var res target[minIdx] - h res rec(l, minIdx - 1, target[minIdx]) res rec(minIdx 1, r, target[minIdx]) return res } return rec(0, target.size - 1, 0) } }Swiftclass SegmentTree { private var A: [Int] private var tree: [Int] private var n: Int init(_ arr: [Int]) { var pow2 1 while pow2 arr.count { pow2 1 } n pow2 A Array(repeating: Int.max, count: n) for i in 0..arr.count { A[i] arr[i] } tree Array(repeating: 0, count: 2 * n) build() } private func build() { for i in 0..n { tree[n i] i } for i in stride(from: n - 1, through: 1, by: -1) { let a tree[i 1] let b tree[(i 1) | 1] tree[i] A[a] A[b] ? a : b } } func query(_ ql: Int, _ qh: Int) - Int { return queryHelper(1, 0, n - 1, ql, qh) } private func queryHelper(_ node: Int, _ l: Int, _ h: Int, _ ql: Int, _ qh: Int) - Int { if ql h || qh l { return -1 } if l ql h qh { return tree[node] } let mid (l h) 1 let a queryHelper(node 1, l, mid, ql, qh) let b queryHelper((node 1) | 1, mid 1, h, ql, qh) if a -1 { return b } if b -1 { return a } return A[a] A[b] ? a : b } } class Solution { func minNumberOperations(_ target: [Int]) - Int { let seg SegmentTree(target) func rec(_ l: Int, _ r: Int, _ h: Int) - Int { if l r { return 0 } let minIdx seg.query(l, r) var res target[minIdx] - h res rec(l, minIdx - 1, target[minIdx]) res rec(minIdx 1, r, target[minIdx]) return res } return rec(0, target.count - 1, 0) } }Ruststruct SegmentTree { a: Veci32, tree: Vecusize, n: usize, } impl SegmentTree { fn new(arr: [i32]) - Self { let mut n 1; while n arr.len() { n 1; } let mut a vec![i32::MAX; n]; a[..arr.len()].copy_from_slice(arr); let mut st Self { a, tree: vec![0; 2 * n], n }; st.build(); st } fn build(mut self) { for i in 0..self.n { self.tree[self.n i] i; } for i in (1..self.n).rev() { let a self.tree[i 1]; let b self.tree[(i 1) | 1]; self.tree[i] if self.a[a] self.a[b] { a } else { b }; } } fn query(self, ql: usize, qh: usize) - usize { self._query(1, 0, self.n - 1, ql, qh) } fn _query(self, node: usize, l: usize, h: usize, ql: usize, qh: usize) - usize { if ql h || qh l { return usize::MAX; } if l ql h qh { return self.tree[node]; } let mid (l h) 1; let a self._query(node 1, l, mid, ql, qh); let b self._query((node 1) | 1, mid 1, h, ql, qh); if a usize::MAX { return b; } if b usize::MAX { return a; } if self.a[a] self.a[b] { a } else { b } } } impl Solution { pub fn min_number_operations(target: Veci32) - i32 { let seg SegmentTree::new(target); fn rec(target: [i32], seg: SegmentTree, l: i32, r: i32, h: i32) - i32 { if l r { return 0; } let min_idx seg.query(l as usize, r as usize); let res target[min_idx] - h; res rec(target, seg, l, min_idx as i32 - 1, target[min_idx]) rec(target, seg, min_idx as i32 1, r, target[min_idx]) } rec(target, seg, 0, target.len() as i32 - 1, 0) } }时间复杂度与空间复杂度时间复杂度O(n log n)——每次区间最小值查询 O(log n)分治共产生 O(n) 次查询空间复杂度O(n)——线段树数组占用 O(n) 空间。解法三贪心Greedy最优解直觉从左到右观察涂色过程。对于第一个元素从 0 开始必须用target[0]次操作才能建起来。对于后续每个元素如果它比前一个高target[i] target[i-1]说明之前的横条纹够不到这个高度必须新增target[i] - target[i-1]次操作来把笔触向上延伸如果它比前一个矮或相等则已有的横条纹可以自然覆盖它——要么继续延伸要么提前收笔不需要任何新操作。核心洞察因此可以浓缩为一句话只有在高度上升时才需要新的操作。总操作数 第一个元素的值 所有相邻正增量的累加和。算法步骤用target[0]初始化结果第一个元素需要这么多操作遍历后续每个元素若target[i] target[i-1]把差值累加到结果否则什么都不加已有操作已经覆盖返回结果。代码实现Pythonclass Solution: def minNumberOperations(self, target: List[int]) - int: res target[0] for i in range(1, len(target)): res max(target[i] - target[i - 1], 0) return resJavapublic class Solution { public int minNumberOperations(int[] target) { int res target[0]; for (int i 1; i target.length; i) { res Math.max(target[i] - target[i - 1], 0); } return res; } }Cclass Solution { public: int minNumberOperations(vectorint target) { int res target[0]; for (int i 1; i target.size(); i) { res max(target[i] - target[i - 1], 0); } return res; } };JavaScriptclass Solution { /** * param {number[]} target * return {number} */ minNumberOperations(target) { let res target[0]; for (let i 1; i target.length; i) { res Math.max(target[i] - target[i - 1], 0); } return res; } }C#public class Solution { public int MinNumberOperations(int[] target) { int res target[0]; for (int i 1; i target.Length; i) { res Math.Max(target[i] - target[i - 1], 0); } return res; } }Gofunc minNumberOperations(target []int) int { res : target[0] for i : 1; i len(target); i { if target[i] target[i-1] { res target[i] - target[i-1] } } return res }Kotlinclass Solution { fun minNumberOperations(target: IntArray): Int { var res target[0] for (i in 1 until target.size) { res maxOf(target[i] - target[i - 1], 0) } return res } }Swiftclass Solution { func minNumberOperations(_ target: [Int]) - Int { var res target[0] for i in 1..target.count { res max(target[i] - target[i - 1], 0) } return res } }Rustimpl Solution { pub fn min_number_operations(target: Veci32) - i32 { let mut res target[0]; for i in 1..target.len() { res (target[i] - target[i - 1]).max(0); } res } }时间复杂度与空间复杂度时间复杂度O(n)——单趟从左到右扫描空间复杂度O(1)——只使用常数个变量。常见误区Common Pitfalls原文档总结了五个高频踩坑点逐一说明如下误区一试图显式追踪实际子数组常见错误是试图模拟每次到底给哪些子数组 1去维护这些子数组的边界和重叠关系。这会导致代码复杂且低效。正确认知是你只需要数新增的层数/笔触数而这恰好发生在高度从上一个元素上升到当前元素的时刻。贪心公式target[0] sum(max(target[i] - target[i-1], 0) for i in range(1, n))不需要显式追踪任何子数组即可完整刻画答案。误区二忘记用第一个元素初始化结果必须以target[0]起步而不是 0。第一个元素从 0 建起恰好需要target[0]次操作与后面元素无关。若从 0 开始只累加正差值会漏掉构建第一个元素所需的所有操作最终答案比正确值少target[0]。误区三把上升和下降的逻辑搞反贪心解法只在target[i] target[i-1]时累加下降时不加。因为高度下降时已有的横条纹天然覆盖了较低的位置不需要新增操作如果错误地在下降时也累加比如试图收尾之前的操作就会重复计数导致答案偏大。误区四大数组场景下选错算法O(n²) 的分治模拟与 O(n log n) 的线段树版本都能通过本题的数据规模但 O(n) 的贪心显然更简单、更快。如果你发现自己正在写线段树或分治请退一步思考一个从左到右的单趟扫描能否解决数上升沿是涂色/增量构造类问题中非常通用的贪心模式值得形成肌肉记忆。误区五累加过程中的整数溢出当数组很长且元素值很大时所有正增量之和可能超过 32 位整数上限。虽然本题的约束通常不会触发溢出但积累大和时仍要保持警惕如果约束允许极大值或极多元素应使用 64 位整数Java 的long、C 的long long、C# 的long、Kotlin 的Long、Go 的int64等。三解法对比与选择建议解法核心思想时间复杂度空间复杂度适用场景分治模拟找区间最小值作地板切分递归求解左右子区间O(n²)O(n)理解问题结构、入门教学线段树用线段树把区间最小值查询降到 O(log n)分治逻辑不变O(n log n)O(n)掌握线段树在分治中的加速作用贪心只累加target[0]与所有相邻正增量O(n)O(1)竞赛与面试的最优解选择建议面试与实战中直接给出 O(n) 贪心即可若面试官追问优化过程可以从分治模拟为什么慢找最小值为 O(n)切入自然引出线段树版本最后再收敛到数上升沿的贪心洞察——这本身就是一条非常完整的思维演进链。本文完整实现收录于 articles/minimum-number-of-increments-on-subarrays-to-form-a-target-array.md可作为多语言对照复习的索引同类区间增量 / 高度分层思维还可见于 trapping-rain-water.md、maximum-subarray.md 与 minimum-number-of-operations-to-make-array-continuous.md。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考