1499. 满足不等式的最大值 [hard]

https://leetcode-cn.com/problems/max-value-of-equation/

给你一个数组 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^5
points[i].length == 2
-10^8 <= points[i][0], points[i][1] <= 10^8
0 <= k <= 2 * 10^8
对于所有的1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。

通过次数991 | 提交次数2,752

Second Try

2020-07-05

传说中的单调队列，看了题解的提示，还是没能在写完priority queue之后写出来。再仔细看了一会儿，才知道这个所谓的单调队列是什么东西。其实就是一个简化版的优先队列，或者说是有序队列。每次插入的时候都进行上浮，实现了一个有序的效果。本来上浮操作O(N)的复杂度是比优先队列的O(lgN)高的,但是一路上浮一路删除，最后速度也就不慢了。

在获取数据的时候，依然是按照浮动窗口的原则，对那些过期的进行删除。

class Solution(object):
    def findMaxValueOfEquation(self, points, k):
        """
        :type points: List[List[int]]
        :type k: int
        :rtype: int
        """
        # max: xj + yj + (yi - xi), xj - xi <= k
        # 怎么就单调了？yi - xi总归不是越来越大的吧
        # 看起来单调队列的意思是自己维护一个优先队列的样子
        # 因为一路往前走，只要维护最近k个距离内最大的yi - xi即可
        deque = []
        maxv  = float('-inf')
        for x, y in points:
            # 依然是清除掉前面那些已经太旧的，而且由于有最后一步的操作，整个队列都是有序的，依次降低
            while len(deque) and  x - deque[0][1] > k:
                deque.pop(0)
            # 类似于priority queue, 只需要对第一个最大的元素进行处理即可
            if len(deque):
                maxv = max(maxv, x + y + deque[0][0])
            # 清除掉后面那些太旧的，或者太小的，这样对比priority queue能够降低上浮时候的时间
            while len(deque) and (deque[-1][0] < y - x or x - deque[0][1] > k):
                deque.pop()
            deque.append((y - x, x))
        return maxv

执行用时：292 ms, 在所有 Python 提交中击败了42.31%的用户
内存消耗：46.9 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-05

有些容易出问题的写法，写在注释里了。

重点是在推入优先队列的时候，按照顺序一遍推入一遍处理，这样才能保证在队列里的都是比当前点位置更靠前的元素。如果一股脑先推进去，次序方面就很难处理了。

import heapq
class Solution(object):
    def findMaxValueOfEquation(self, points, k):
        """
        :type points: List[List[int]]
        :type k: int
        :rtype: int
        """
        # max: xj + yj + (yi - xi), xj - xi <= k

        # 这个写法就麻烦了，一下子把所有内容塞到队列里，没有找到xj前面k个点内yi - xi的最大值
        # heap = []
        # for x, y in points:
        #     heapq.heappush((y - x, x))
        # maxv = 0
        # for x, y in points:
        #     heapq.

        heap = []
        maxv = float('-inf')  #竟然还有负值，导致无法使用0
        for x, y in points:
            while heap:
                # heapq.nsmallest取第一个最小值是超时写法， 直接用heap[0]竟然就不超时了
                # first = heapq.nsmallest(1, heap)[0]
                first = heap[0]
                # print(first)
                if x - first[1] <= k:
                    # first仍然保存在heap中，后面可能还有用
                    maxv = max(maxv, x + y - first[0])
                    break
                else:
                    # 在x,y此处都已经超过k了，x, y后面的肯定更超过，直接无视了
                    heapq.heappop(heap)
            # 额外添加进去，这样不会导致取到重复的内容
            heapq.heappush(heap, (-(y - x), x))  # 取负值
        return maxv

执行用时：276 ms, 在所有 Python 提交中击败了65.38%的用户
内存消耗：47.3 MB, 在所有 Python 提交中击败了100.00%的用户