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），問題如何轉化為分段線性回歸？
- 若點的順序不固定（不一定按天數排列），而是要找最少的直線覆蓋所有點（不一定按順序連接），問題的本質會如何改變？