LeetCode 題解Minimum Number of Increments on Subarrays to Form a Target Array——從分治模擬到線段樹(shù)再到單趟貪心的三階演進(jìn)【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode導(dǎo)讀本文基于本倉(cāng)庫(kù)的 articles/minimum-number-of-increments-on-subarrays-to-form-a-target-array.md 展開(kāi)系統(tǒng)講解 LeetCode 經(jīng)典問(wèn)題Minimum Number of Increments on Subarrays to Form a Target Array將全零數(shù)組通過(guò)每次對(duì)連續(xù)子數(shù)組 1的操作用最少次數(shù)構(gòu)造成目標(biāo)數(shù)組。文章完整覆蓋三種解法O(n2) 的分治模擬、O(n log n) 的線段樹(shù)優(yōu)化以及 O(n) 的單趟貪心并給出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九種語(yǔ)言的完整實(shí)現(xiàn)與復(fù)雜度分析。讀完本文你將掌握按層涂色的分治思想、用線段樹(shù)把區(qū)間最小值查詢(xún)降到 O(log n) 的技巧以及只數(shù)上升沿這一貪心模式的推導(dǎo)過(guò)程能夠從容應(yīng)對(duì)同類(lèi)區(qū)間增量構(gòu)造問(wèn)題。前置知識(shí)Prerequisites在嘗試解決本題之前建議先熟悉以下四塊基礎(chǔ)能力它們分別對(duì)應(yīng)三種解法的底層支撐分治Divide and Conquer——在關(guān)鍵點(diǎn)例如最小值所在位置處把問(wèn)題拆分成相互獨(dú)立的子問(wèn)題是解法一的骨架線段樹(shù)Segment Tree——支持高效的區(qū)間最小值查詢(xún)用于把解法一中的線性掃描替換為對(duì)數(shù)級(jí)查詢(xún)從而優(yōu)化整體復(fù)雜度是解法二的核心數(shù)據(jù)結(jié)構(gòu)貪心算法Greedy——識(shí)別出統(tǒng)計(jì)上升段就能直接得到最優(yōu)答案是解法三的洞察來(lái)源數(shù)組遍歷Array Traversal——單趟處理相鄰元素的差值是貪心解法的落地手段。需要說(shuō)明的是本倉(cāng)庫(kù)是一個(gè)多語(yǔ)言 LeetCode 題解倉(cāng)庫(kù)詳見(jiàn) README.md上述前置知識(shí)點(diǎn)中分治 最小值切分的思路在倉(cāng)庫(kù)的 maximum-subarray.md、merge-intervals.md 等區(qū)間類(lèi)文章中有大量呼應(yīng)而根據(jù)相鄰元素差值決定是否新增操作的貪心模式與 trapping-rain-water.md 這類(lèi)按高度/層數(shù)思考的題目思路一致可以互相印證。問(wèn)題建模把數(shù)組看作一層一層的橫條紋在進(jìn)入三種解法之前先建立一個(gè)貫穿全文的直覺(jué)模型把 target 數(shù)組想象成一幅由水平條紋堆疊出來(lái)的柱狀圖。每次操作把某個(gè)連續(xù)子數(shù)組整體 1等價(jià)于在該子數(shù)組覆蓋的柱子上多涂一層橫條紋。目標(biāo)是用最少的涂層次數(shù)把高度從 0 堆疊成 target 所描述的輪廓。這個(gè)模型直接導(dǎo)出了解法一的分治視角某個(gè)區(qū)間內(nèi)的最小值就是該區(qū)間的地板地板以下的層數(shù)必須先一次性涂滿然后再分別在最小值的左右兩側(cè)獨(dú)立地往上繼續(xù)涂。三種解法的共同點(diǎn)是都在回答同一個(gè)問(wèn)題每一層橫條紋最多能連續(xù)覆蓋多長(zhǎng)差別只在于統(tǒng)計(jì)方式——是遞歸找最小值分治、用數(shù)據(jù)結(jié)構(gòu)加速找最小值線段樹(shù)還是直接數(shù)上升沿貪心。解法一分治模擬Simulation直覺(jué)把構(gòu)建 target 數(shù)組的過(guò)程想象成按水平層涂色。每次操作對(duì)連續(xù)子數(shù)組 1就像涂一層顏色。遞歸地執(zhí)行在當(dāng)前區(qū)間[l, r]內(nèi)找到最小值把從當(dāng)前高度到該最小值的所有層一次性涂滿需要min_value - current_height次操作最小值把區(qū)間切分成左右兩個(gè)互不相干的部分分別遞歸處理。關(guān)鍵點(diǎn)在于最小值充當(dāng)了地板它把問(wèn)題隔離成兩個(gè)獨(dú)立的子問(wèn)題——左側(cè)和右側(cè)的柱子永遠(yuǎn)不會(huì)共享同一筆跨過(guò)最小值的涂層因此可以分開(kāi)獨(dú)立求解。算法步驟定義遞歸函數(shù)參數(shù)為左邊界l、右邊界r、當(dāng)前已涂高度h遞歸出口若l r返回0在區(qū)間內(nèi)線性掃描找到最小值所在下標(biāo)minIdx把target[minIdx] - h累加到結(jié)果即到達(dá)該最小值所需新增的層數(shù)以target[minIdx]作為新的高度遞歸求解左半部分[l, minIdx - 1]與右半部分[minIdx 1, r]返回三部分之和。代碼實(shí)現(xiàn)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) } }時(shí)間復(fù)雜度與空間復(fù)雜度時(shí)間復(fù)雜度O(n2)——最壞情況如單調(diào)遞減數(shù)組下每次遞歸都要線性掃描整個(gè)區(qū)間找最小值空間復(fù)雜度O(n)——遞歸棧深度在最壞情況下為 O(n)例如最小值總在端點(diǎn)退化為鏈?zhǔn)竭f歸。解法二線段樹(shù)優(yōu)化Segment Tree直覺(jué)解法一之所以慢是因?yàn)槊看卧趨^(qū)間內(nèi)找最小值都要 O(n) 線性掃描。線段樹(shù)可以把區(qū)間最小值查詢(xún)壓縮到 O(log n)整體分治邏輯完全不變?nèi)匀辉谧钚≈堤幥蟹种徊贿^(guò)把掃描找最小替換成查線段樹(shù)。這樣一來(lái)總時(shí)間復(fù)雜度從 O(n2) 降為 O(n log n)。算法步驟構(gòu)建一棵線段樹(shù)樹(shù)的每個(gè)節(jié)點(diǎn)存儲(chǔ)對(duì)應(yīng)區(qū)間內(nèi)最小值所在的下標(biāo)注意存下標(biāo)而非值因?yàn)楹罄m(xù)遞歸需要按位置切分沿用同樣的遞歸分治流程查詢(xún)線段樹(shù)得到當(dāng)前區(qū)間[l, r]內(nèi)最小值下標(biāo)minIdx把target[minIdx] - h最小值與當(dāng)前高度之差累加到結(jié)果遞歸處理左子區(qū)間[l, minIdx - 1]與右子區(qū)間[minIdx 1, r]返回累計(jì)的操作總數(shù)。實(shí)現(xiàn)細(xì)節(jié)上所有語(yǔ)言都采用了把數(shù)組長(zhǎng)度補(bǔ)齊到 2 的冪的技巧多出的位置填充無(wú)窮大INF這樣線段樹(shù)可以被組織成滿二叉樹(shù)直接用2 * n大小的數(shù)組存儲(chǔ)父子節(jié)點(diǎn)通過(guò)j 1與(j 1) | 1訪問(wèn)。Python 版的SegmentTree還額外提供了update方法單點(diǎn)更新后沿路徑向上重算說(shuō)明該類(lèi)是一個(gè)可復(fù)用的通用最小值下標(biāo)線段樹(shù)不只是為本題定制。代碼實(shí)現(xiàn)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說(shuō)明Python 版將遞歸改寫(xiě)為顯式棧效果等價(jià)于解法一的遞歸流程同時(shí)避免了 Python 默認(rèn)遞歸深度限制帶來(lái)的風(fēng)險(xiǎn)其余語(yǔ)言版本保留了遞歸寫(xiě)法。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) } }時(shí)間復(fù)雜度與空間復(fù)雜度時(shí)間復(fù)雜度O(n log n)——每次區(qū)間最小值查詢(xún) O(log n)分治共產(chǎn)生 O(n) 次查詢(xún)空間復(fù)雜度O(n)——線段樹(shù)數(shù)組占用 O(n) 空間。解法三貪心Greedy最優(yōu)解直覺(jué)從左到右觀察涂色過(guò)程。對(duì)于第一個(gè)元素從 0 開(kāi)始必須用target[0]次操作才能建起來(lái)。對(duì)于后續(xù)每個(gè)元素如果它比前一個(gè)高target[i] target[i-1]說(shuō)明之前的橫條紋夠不到這個(gè)高度必須新增target[i] - target[i-1]次操作來(lái)把筆觸向上延伸如果它比前一個(gè)矮或相等則已有的橫條紋可以自然覆蓋它——要么繼續(xù)延伸要么提前收筆不需要任何新操作。核心洞察因此可以濃縮為一句話只有在高度上升時(shí)才需要新的操作?？偛僮鲾?shù) 第一個(gè)元素的值 所有相鄰正增量的累加和。算法步驟用target[0]初始化結(jié)果第一個(gè)元素需要這么多操作遍歷后續(xù)每個(gè)元素若target[i] target[i-1]把差值累加到結(jié)果否則什么都不加已有操作已經(jīng)覆蓋返回結(jié)果。代碼實(shí)現(xiàn)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 } }時(shí)間復(fù)雜度與空間復(fù)雜度時(shí)間復(fù)雜度O(n)——單趟從左到右掃描空間復(fù)雜度O(1)——只使用常數(shù)個(gè)變量。常見(jiàn)誤區(qū)Common Pitfalls原文檔總結(jié)了五個(gè)高頻踩坑點(diǎn)逐一說(shuō)明如下誤區(qū)一試圖顯式追蹤實(shí)際子數(shù)組常見(jiàn)錯(cuò)誤是試圖模擬每次到底給哪些子數(shù)組 1去維護(hù)這些子數(shù)組的邊界和重疊關(guān)系。這會(huì)導(dǎo)致代碼復(fù)雜且低效。正確認(rèn)知是你只需要數(shù)新增的層數(shù)/筆觸數(shù)而這恰好發(fā)生在高度從上一個(gè)元素上升到當(dāng)前元素的時(shí)刻。貪心公式target[0] sum(max(target[i] - target[i-1], 0) for i in range(1, n))不需要顯式追蹤任何子數(shù)組即可完整刻畫(huà)答案。誤區(qū)二忘記用第一個(gè)元素初始化結(jié)果必須以target[0]起步而不是 0。第一個(gè)元素從 0 建起恰好需要target[0]次操作與后面元素?zé)o關(guān)。若從 0 開(kāi)始只累加正差值會(huì)漏掉構(gòu)建第一個(gè)元素所需的所有操作最終答案比正確值少target[0]。誤區(qū)三把上升和下降的邏輯搞反貪心解法只在target[i] target[i-1]時(shí)累加下降時(shí)不加。因?yàn)楦叨认陆禃r(shí)已有的橫條紋天然覆蓋了較低的位置不需要新增操作如果錯(cuò)誤地在下降時(shí)也累加比如試圖收尾之前的操作就會(huì)重復(fù)計(jì)數(shù)導(dǎo)致答案偏大。誤區(qū)四大數(shù)組場(chǎng)景下選錯(cuò)算法O(n2) 的分治模擬與 O(n log n) 的線段樹(shù)版本都能通過(guò)本題的數(shù)據(jù)規(guī)模但 O(n) 的貪心顯然更簡(jiǎn)單、更快。如果你發(fā)現(xiàn)自己正在寫(xiě)線段樹(shù)或分治請(qǐng)退一步思考一個(gè)從左到右的單趟掃描能否解決數(shù)上升沿是涂色/增量構(gòu)造類(lèi)問(wèn)題中非常通用的貪心模式值得形成肌肉記憶。誤區(qū)五累加過(guò)程中的整數(shù)溢出當(dāng)數(shù)組很長(zhǎng)且元素值很大時(shí)所有正增量之和可能超過(guò) 32 位整數(shù)上限。雖然本題的約束通常不會(huì)觸發(fā)溢出但積累大和時(shí)仍要保持警惕如果約束允許極大值或極多元素應(yīng)使用 64 位整數(shù)Java 的long、C 的long long、C# 的long、Kotlin 的Long、Go 的int64等。三解法對(duì)比與選擇建議解法核心思想時(shí)間復(fù)雜度空間復(fù)雜度適用場(chǎng)景分治模擬找區(qū)間最小值作地板切分遞歸求解左右子區(qū)間O(n2)O(n)理解問(wèn)題結(jié)構(gòu)、入門(mén)教學(xué)線段樹(shù)用線段樹(shù)把區(qū)間最小值查詢(xún)降到 O(log n)分治邏輯不變O(n log n)O(n)掌握線段樹(shù)在分治中的加速作用貪心只累加target[0]與所有相鄰正增量O(n)O(1)競(jìng)賽與面試的最優(yōu)解選擇建議面試與實(shí)戰(zhàn)中直接給出 O(n) 貪心即可若面試官追問(wèn)優(yōu)化過(guò)程可以從分治模擬為什么慢找最小值為 O(n)切入自然引出線段樹(shù)版本最后再收斂到數(shù)上升沿的貪心洞察——這本身就是一條非常完整的思維演進(jìn)鏈。本文完整實(shí)現(xiàn)收錄于 articles/minimum-number-of-increments-on-subarrays-to-form-a-target-array.md可作為多語(yǔ)言對(duì)照復(fù)習(xí)的索引同類(lèi)區(qū)間增量 / 高度分層思維還可見(jiàn)于 trapping-rain-water.md、maximum-subarray.md 與 minimum-number-of-operations-to-make-array-continuous.md?！久赓M(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考