表示一个折线图的最少线段数

标签: 几何 数组 数学 数论 排序

难度: Medium

给你一个二维整数数组 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 <= 105
  • stockPrices[i].length == 2
  • 1 <= dayi, pricei <= 109
  • 所有 dayi 互不相同 。

Submission

运行时间: 154 ms

内存: 48.9 MB

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        stockPrices.sort(key=lambda x: x[0])  # 按照 day 排序
        ans, pre_dy, pre_dx = 0, 1, 0
        for (x1, y1), (x2, y2) in pairwise(stockPrices):
            dy, dx = y2 - y1, x2 - x1
            if dy * pre_dx != pre_dy * dx:  # 与上一条线段的斜率不同
                ans += 1
                pre_dy, pre_dx = dy, dx
        return ans

Explain

此题解的思路是首先将股票价格按日期排序，然后遍历排序后的价格，计算每两个相邻点之间的斜率，如果当前线段的斜率与上一条线段的斜率不同，则需要另起一条线段。最终返回线段的数量。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        stockPrices.sort(key=lambda x: x[0])  # 按照 day 排序
        ans, pre_dy, pre_dx = 0, 1, 0  # 初始化线段数为0，以及前一个斜率的分子分母
        for (x1, y1), (x2, y2) in pairwise(stockPrices):  # 遍历相邻的两个点
            dy, dx = y2 - y1, x2 - x1  # 计算当前线段的斜率
            if dy * pre_dx != pre_dy * dx:  # 如果当前斜率与前一个斜率不同
                ans += 1  # 需要增加一条线段
                pre_dy, pre_dx = dy, dx  # 更新前一个斜率
        return ans  # 返回线段数

Explore

排序操作确保了股票价格的数据是按日期顺序处理的，这对于计算相邻两点之间的斜率并判断是否需要新的线段至关重要。如果输入数据已经是按日期排序的，理论上这一步不是必要的，但在实际应用中，为了确保程序的健壮性和正确性，通常还是会进行排序，除非能够完全确认数据的顺序正确。

直接计算斜率可能涉及浮点数运算，这可能导致精度问题和浮点数不稳定性。通过比较两个斜率的交叉乘积（dy * pre_dx 与 pre_dy * dx）可以避免浮点运算，从而避免精度误差，确保斜率比较的准确性。

这种比较方式通过整数的乘积来避免了使用浮点数，从而消除了因浮点数精度导致的误差。通过交叉相乘的方式，只要两个斜率不相等，它们的交叉乘积结果就会不同。这种方法在整数运算范围内是准确的，不会出现计算误差。

题解中应该在遍历点之前将`ans`初始化为1，因为至少一条线段是必需的，即使所有点都共线。如果所有点共线，按照当前逻辑，初始化为0会导致错误的输出。正确的做法是在遍历前，假设至少有一条线段，然后在遍历中根据需要增加线段数。