LeetCode 题解工作台
表示一个折线图的最少线段数
给你一个二维整数数组 stockPrices ，其中 stockPrices[i] = [day i , price i ] 表示股票在 day i 的价格为 price i 。 折线图 是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
需要注意： 1. 只有一个点时，需要的线段数为 0；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个二维整数数组 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互不相同 。
解题思路
方法一：斜率比较
需要注意：
- 只有一个点时，需要的线段数为 0；
- 利用除法计算斜率时，会有浮点误差，可以改成乘法比较。
class Solution:
def minimumLines(self, stockPrices: List[List[int]]) -> int:
stockPrices.sort()
dx, dy = 0, 1
ans = 0
for (x, y), (x1, y1) in pairwise(stockPrices):
dx1, dy1 = x1 - x, y1 - y
if dy * dx1 != dx * dy1:
ans += 1
dx, dy = dx1, dy1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is dominated by sorting, O(n log n), and slope checks take O(n), giving overall O(n log n). Space complexity is O(1) extra if in-place sorting is used. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask why sorting by day is necessary before checking slopes.
- question_mark
Expect candidate to explain slope comparison without floating-point precision errors.
- question_mark
Look for handling of edge cases where multiple points are collinear or duplicate prices exist.
常见陷阱
外企场景- error
Not sorting points by day before checking slopes, leading to incorrect line counts.
- error
Using floating-point division for slopes without reducing fractions, causing precision errors.
- error
Failing to handle cases where consecutive points have the same price or day order is not guaranteed.
进阶变体
外企场景- arrow_right_alt
Calculate minimum lines if some points can be skipped or ignored to reduce total lines.
- arrow_right_alt
Determine the number of lines needed for a 3D line chart instead of 2D.
- arrow_right_alt
Optimize for streaming input where points arrive one by one and minimum lines must be updated online.