題目描述: 給定一組股票價格 stockPrices[i] = [day, price],求最少需要幾條線段來連接所有點以形成折線圖。
解題思路: 將點按天數排序後,若連續三個點共線,則中間那個點不會增加新的線段。否則需要一條新的線段。
時間複雜度: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 比較緩解,但不建議在面試中使用。