满足不等式的最大值【LC1499】
给你一个数组
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的点。
新知识++
- 思路
class Solution { public int findMaxValueOfEquation(int[][] points, int k) { int ans = Integer.MIN_VALUE; var q = new ArrayDeque<int[]>(); for (var p : points) { int x = p[0], y = p[1]; while (!q.isEmpty() && q.peekFirst()[0] < x - k) // 队首超出范围 q.pollFirst(); // 弹它！ if (!q.isEmpty()) ans = Math.max(ans, x + y + q.peekFirst()[1]); // 加上最大的 yi-xi while (!q.isEmpty() && q.peekLast()[1] <= y - x) // 队尾不如新来的强 q.pollLast(); // 弹它！ q.addLast(new int[]{x, y - x}); } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/max-value-of-equation/solutions/2352457/on-dan-diao-dui-lie-fu-ti-dan-pythonjava-hhrr/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { public int findMaxValueOfEquation(int[][] points, int k) { int ans = -(1 << 30); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]); for (var p : points) { int x = p[0], y = p[1]; while (!pq.isEmpty() && x - pq.peek()[1] > k) { pq.poll(); } if (!pq.isEmpty()) { ans = Math.max(ans, x + y + pq.peek()[0]); } pq.offer(new int[] {y - x, x}); } return ans; } } 作者：ylb 链接：https://leetcode.cn/problems/max-value-of-equation/solutions/2352475/python3javacgotypescript-yi-ti-shuang-ji-dtrj/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
