表示一个折线图的最少线段数
难度:
标签:
题目描述
给你一个二维整数数组 stockPrices ，其中 stockPrices[i] = [dayi, pricei] 表示股票在 dayi 的价格为 pricei 。折线图 是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：
请你返回要表示一个折线图所需要的 最少线段数 。
示例 1：
输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]] 输出：3 解释： 上图为输入对应的图，横坐标表示日期，纵坐标表示价格。 以下 3 个线段可以表示折线图： - 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。 - 线段 2 （蓝色）从 (4,4) 到 (5,4) 。 - 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。 可以证明，无法用少于 3 条线段表示这个折线图。
示例 2：
输入：stockPrices = [[3,4],[1,2],[7,8],[2,3]] 输出：1 解释： 如上图所示，折线图可以用一条线段表示。
提示：
1 <= stockPrices.length <= 105stockPrices[i].length == 21 <= dayi, pricei <= 109- 所有
dayi互不相同 。
代码结果
运行时间: 154 ms, 内存: 48.9 MB
/*
* 题目思路：
* 使用 Java Stream，我们可以首先对数组进行排序，然后在进行一次循环计算每次的斜率是否变化。斜率计算使用流来简化代码。
*/
import java.util.*;
public class Solution {
public int minimumLines(int[][] stockPrices) {
Arrays.sort(stockPrices, Comparator.comparingInt(a -> a[0]));
return (int) IntStream.range(1, stockPrices.length - 1)
.filter(i -> {
long dx1 = stockPrices[i][0] - stockPrices[i - 1][0];
long dy1 = stockPrices[i][1] - stockPrices[i - 1][1];
long dx2 = stockPrices[i + 1][0] - stockPrices[i][0];
long dy2 = stockPrices[i + 1][1] - stockPrices[i][1];
return dy1 * dx2 != dy2 * dx1;
})
.count() + 1;
}
}解释
方法:
此题解的思路是首先将股票价格按日期排序，然后遍历排序后的价格，计算每两个相邻点之间的斜率，如果当前线段的斜率与上一条线段的斜率不同，则需要另起一条线段。最终返回线段的数量。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中的排序操作为什么是必须的？如果输入的数据已经是排序过的，这一步还有必要吗？
▷🦆
在计算斜率时，为什么选择用两点间的差值(dy, dx)的比较而不是直接计算斜率的实际值？
▷🦆
题解中提到的`dy * pre_dx != pre_dy * dx`比较操作是如何确保斜率的准确比较的，有没有可能出现计算误差？
▷🦆
函数返回的是线段数，初始化`ans`为0，这是否意味着在所有点都共线的特殊情况下，输出可能不正确？
▷