✨今日算法一题
文章目录
表示一个折线图的最少线段数
题目描述
思路详解
这里我们考虑到，什么时候线段需要加一段，如果两段的斜率变化了，则就要加一段了。
相邻的点如果斜率不一致,需要新加一段
通过相邻点的横纵坐标差,判断斜率,方式有二:
- y1/x1 != y2/x2, 由于除法涉及 double 精度 比较麻烦
- 移项后判断 y1 * x2 != y2 * x1 , 方便很多
一个点, 线段数为0
代码与结果
class Solution { public int minimumLines(int[][] stockPrices) { Arrays.sort(stockPrices, (o1, o2) -> o1[0] - o2[0]); int n = stockPrices.length, res = 1; if (n == 1) return 0; for (int i = 2; i < n; i++) { int x1 = stockPrices[i][0] - stockPrices[i - 1][0], y1 = stockPrices[i][1] - stockPrices[i - 1][1]; int x2 = stockPrices[i - 1][0] - stockPrices[i - 2][0], y2 = stockPrices[i - 1][1] - stockPrices[i - 2][1]; if (y1 * x2 != y2 * x1) res++; } return res; } }
✨总结
本题考察了数学思想，判断斜率进而判断线段的数量。
