Medium

题目描述

给你一个二维整数数组 stockPrices，其中 stockPrices[i] = [dayi, pricei] 表示第 dayi 天的股票价格是 pricei。

通过在 XY 平面上绘制点并连接相邻点来从数组创建折线图，其中 X 轴表示天数，Y 轴表示价格。

返回表示折线图所需的最少线段数。

示例 1：

输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
输出：3
解释：
上图表示输入，X 轴表示天数，Y 轴表示价格。
可以画以下 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 <= 10^5
  • stockPrices[i].length == 2
  • 1 <= dayi, pricei <= 10^9
  • 所有 dayi 都是不同的

解题思路

这道题的核心思想是判断相邻的线段是否共线。如果多个连续的点在同一条直线上，它们可以用一条线段表示；否则需要多条线段。

解题思路：

  1. 首先将股票价格数组按天数排序，因为题目要求连接相邻的点
  2. 计算相邻两点之间的斜率，如果连续的线段斜率相同，说明它们在同一条直线上
  3. 当斜率发生变化时，需要增加一条新的线段

关键技巧：

  • 直接计算斜率可能遇到除零问题和精度问题
  • 使用交叉相乘来避免除法运算：对于点 (x1,y1), (x2,y2), (x3,y3)，如果 (y2-y1)/(x2-x1) == (y3-y2)/(x3-x2)，等价于 (y2-y1)(x3-x2) == (y3-y2)(x2-x1)

边界情况：

  • 如果只有一个点，不需要线段，返回 0
  • 如果只有两个点，只需要一条线段

时间复杂度主要由排序决定，空间复杂度为常数级别。

代码实现

class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        int n = stockPrices.size();
        if (n <= 1) return 0;
        if (n == 2) return 1;
        
        sort(stockPrices.begin(), stockPrices.end());
        
        int lines = 1;
        for (int i = 2; i < n; i++) {
            long long x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];
            long long x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];
            long long x3 = stockPrices[i][0], y3 = stockPrices[i][1];
            
            // Check if slopes are different using cross multiplication
            // (y2-y1)/(x2-x1) != (y3-y2)/(x3-x2)
            // Equivalent to: (y2-y1)*(x3-x2) != (y3-y2)*(x2-x1)
            if ((y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)) {
                lines++;
            }
        }
        
        return lines;
    }
};

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        n = len(stockPrices)
        if n <= 1:
            return 0
        if n == 2:
            return 1
        
        stockPrices.sort()
        
        lines = 1
        for i in range(2, n):
            x1, y1 = stockPrices[i-2]
            x2, y2 = stockPrices[i-1]
            x3, y3 = stockPrices[i]
            
            # Check if slopes are different using cross multiplication
            # (y2-y1)/(x2-x1) != (y3-y2)/(x3-x2)
            # Equivalent to: (y2-y1)*(x3-x2) != (y3-y2)*(x2-x1)
            if (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1):
                lines += 1
        
        return lines

public class Solution {
    public int MinimumLines(int[][] stockPrices) {
        int n = stockPrices.Length;
        if (n <= 1) return 0;
        if (n == 2) return 1;
        
        Array.Sort(stockPrices, (a, b) => a[0].CompareTo(b[0]));
        
        int lines = 1;
        for (int i = 2; i < n; i++) {
            long x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];
            long x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];
            long x3 = stockPrices[i][0], y3 = stockPrices[i][1];
            
            // Check if slopes are different using cross multiplication
            // (y2-y1)/(x2-x1) != (y3-y2)/(x3-x2)
            // Equivalent to: (y2-y1)*(x3-x2) != (y3-y2)*(x2-x1)
            if ((y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)) {
                lines++;
            }
        }
        
        return lines;
    }
}

var minimumLines = function(stockPrices) {
    const n = stockPrices.length;
    if (n <= 1) return 0;
    if (n == 2) return 1;
    
    stockPrices.sort((a, b) => a[0] - b[0]);
    
    let lines = 1;
    for (let i = 2; i < n; i++) {
        const [x1, y1] = stockPrices[i-2];
        const [x2, y2] = stockPrices[i-1];
        const [x3, y3] = stockPrices[i];
        
        // Check if slopes are different using cross multiplication
        // (y2-y1)/(x2-x1) != (y3-y2)/(x3-x2)
        // Equivalent to: (y2-y1)*(x3-x2) != (y3-y2)*(x2-x1)
        if ((y2 - y1) * (x3 - x2) !== (y3 - y2) * (x2 - x1)) {
            lines++;
        }
    }
    
    return lines;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：O(n log n)，主要由排序操作决定，遍历数组的时间复杂度为 O(n)
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

相关题目