2280. Minimum Lines to Represent a Line Chart

Question

You are given a 2D integer array stockPrices where stockPrices[i] = [day<sub>i</sub>, price<sub>i</sub>] indicates the price of the stock on day day<sub>i</sub> is price<sub>i</sub>. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:

Solution

如果只有一个点，无法组成线段则返回0。否则至少可以组成1条线段。

首先将所有点根据x的位置排序，然后一次比较连续的各个向量的方向。
为了防止除法精度问题，计算两个向量（三个点组成两个向量）的叉乘，如果叉乘为0，则说明两个向量是平行的，此时不需要增加计数。
如果叉乘结果不等于0，则将计数+1。

最后返回计数的结果。

Code

class Solution {
    public int minimumLines(int[][] stockPrices) {
        if(stockPrices.length == 1) return 0;
        
        Arrays.sort(stockPrices, (a,b) -> a[0] - b[0]);
        int count = 1, lastX = 0, lastY = 0;
        
        for(int i = 1; i < stockPrices.length; i++){
            int x = stockPrices[i][0] - stockPrices[i-1][0];
            int y = stockPrices[i][1] - stockPrices[i-1][1];
            
            int k = lastX * y - lastY * x;
            if(k != 0) count++;
            lastX = x;
            lastY = y;
        }
        return count;
    }
}