题目描述
给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。
请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。
题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。
示例 1：
- 输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
- 输出：4
- 解释：前两个点满足 |xi - xj| <= 1 ，代入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。
没有其他满足条件的点，所以返回 4 和 1 中最大的那个。
示例 2：
- 输入：points = [[0,0],[3,0],[9,2]], k = 3
- 输出：3
- 解释：只有前两个点满足 |xi - xj| <= 3 ，代入方程后得到值 0 + 0 + |0 - 3| = 3 。
提示：
2 <= points.length <= 10^5points[i].length == 2-10^8 <= points[i][0], points[i][1] <= 10^80 <= k <= 2 * 10^8- 对于所有的 1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。
解法一：优先队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
type PriorityQueue struct {
arr [][2]int
}
func (pq *PriorityQueue) Len() int {
return len(pq.arr)
}
func (pq *PriorityQueue) Swap(i, j int) {
pq.arr[i], pq.arr[j] = pq.arr[j], pq.arr[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
pq.arr = append(pq.arr, x.([2]int))
}
func (pq *PriorityQueue) Pop() interface{} {
a := pq.arr
ret := a[len(a)-1]
pq.arr = a[:len(a)-1]
return ret
}
func (pq *PriorityQueue) Less(i, j int) bool {
return pq.arr[i][0] > pq.arr[j][0]
}
func max(nums ...int) int {
ans := nums[0]
for _, num := range nums {
if num > ans {
ans = num
}
}
return ans
}
func findMaxValueOfEquation(points [][]int, k int) int {
ans := math.MinInt32
queue := &PriorityQueue{}
heap.Push(queue, [2]int{points[0][1] - points[0][0], points[0][0]})
for i := 1; i < len(points); i++ {
x, y := points[i][0], points[i][1]
for queue.Len() > 0 && x-queue.arr[0][1] > k {
heap.Pop(queue)
}
if queue.Len() > 0 {
ans = max(ans, x+y+queue.arr[0][0])
}
heap.Push(queue, [2]int{y - x, x})
}
return ans
}
|
