ETH官方钱包

前往
大廳
主題

LeetCode - 2280. Minimum Lines to Represent a Line Chart 解題心得

Not In My Back Yard | 2023-04-14 12:00:08 | 巴幣 100 | 人氣 194

題目連結:


題目意譯:
你被給定一個二維整數陣列 stockPrices 其中 stockPrices[i] = [dayi, pricei] 代表著第 dayi 天的價格為 pricei。現在有一個折線圖藉由把該陣列中的數字畫在一個 XY 座標平面上並將各個相鄰的點連線而得,其中 X 軸代表著天數而 Y 軸代表著價格。其中一個例子為下圖所示:

回傳描述該折線圖最少所需的線條。

限制:
1 ≦ stockPrices.length ≦ 10 ^ 5
stockPrices[i].length == 2
1 ≦ dayi, pricei ≦ 10 ^ 9
所有 dayi 彼此相異。



範例測資:
範例 1:
輸入: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
輸出: 3
解釋:
上圖代表著輸入,其中 X 軸代表著天數而 Y 軸代表著價格。
接著 3 條線可以用來表示該折線圖:
- 從 (1,7) 到 (4,4) 的第一條線(以紅色表示),其經過了 (1,7) 、 (2,6) 、 (3,5) 和 (4,4)。
- 從 (4,4) 到 (5,4) 的第二條線(以藍色表示)。
- 從 (5,4) 到 (8,1) 的第三條線(以綠色表示),其經過了 (5,4) 、 (6,3) 、 (7,2) 和 (8,1)。
可以證明不可能使用少於三條線來表示這個折線圖。

範例 2:
輸入: stockPrices = [[3,4],[1,2],[7,8],[2,3]]
輸出: 1
解釋:
如上圖所示,折線圖可以被單一一條線所表示。


解題思維:
先把 stockPrices 中每一個股價價格按照天數由小排到大。而因為每兩個相鄰股價會在折線圖上形成一個「線段」,因此我們掃過每個相鄰股價求出每一個線段的斜率(即「y 座標變化量」與「x 座標變化量」之比例。不用真的求出斜率值,因為會產生浮點數誤差)。

接著掃過相鄰線段的斜率 s1 、 s2。而當兩者的斜率不相等時,代表先前與 s1 同斜率的線段可以用同一條線條表示,並代表著 s2 是一個新線條的開始。

掃完之後便可以知道該折線圖最少用幾個線條表示。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作