MediumRating 1681
2280. Minimum Lines to Represent a Line Chart
arraymathgeometrysortingnumber-theory
解題說明
Minimum Lines to Represent a Line Chart
題目描述: 給定一組股票價格 stockPrices[i] = [day, price],求最少需要幾條線段來連接所有點以形成折線圖。
解題思路: 將點按天數排序後,若連續三個點共線,則中間那個點不會增加新的線段。否則需要一條新的線段。
- 按天數排序所有點。
- 從第二個區間開始,比較當前線段的斜率與前一條線段的斜率。若斜率不同,需要多一條線段。
- 避免浮點數精度問題:不用除法算斜率,改用叉積判斷三點是否共線。
- 三點 A(x1,y1), B(x2,y2), C(x3,y3) 共線 ⟺ (y2-y1)(x3-x2) == (y3-y2)(x2-x1)
- 注意使用 long long 避免整數溢位。
C++ 解法
複雜度分析
時間複雜度:O(n log n) — 排序佔主要時間,後續遍歷 O(n)。
空間複雜度:O(log n) — 排序所需的棧空間(原地排序)。
虛擬碼
1. If n <= 1, return 0. 2. Sort points by day. 3. lines = 1. 4. For i = 2 to n-1: a. Compute dx1 = x[i-1] - x[i-2], dy1 = y[i-1] - y[i-2]. b. Compute dx2 = x[i] - x[i-1], dy2 = y[i] - y[i-1]. c. If dy1 * dx2 != dy2 * dx1: lines++. 5. Return lines.
其他解法
-
分數表示斜率:將斜率用最簡分數 (dy/gcd, dx/gcd) 表示,比較分數是否相等。需要注意正負號的處理和 dy=0 的特殊情況。避免了浮點數但引入了 GCD 計算。
-
浮點數斜率比較:直接用 double 計算 dy/dx 並比較。簡單但有精度風險,特別是當價格差值很大時。可以用 epsilon 比較緩解,但不建議在面試中使用。
延伸思考
- 若允許的誤差為 epsilon(即斜率差小於 epsilon 的線段可以合併),如何修改判斷條件?
- 若要求最少的線段數使得每條線段是最佳擬合(least squares),問題如何轉化為分段線性回歸?
- 若點的順序不固定(不一定按天數排列),而是要找最少的直線覆蓋所有點(不一定按順序連接),問題的本質會如何改變?