Method 1: use heap

class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        #TC: worst (O n log n), average O(n)
        #SC: worst(O(n))

        #Use heap to store maximum of y_i - x_i

        res = -sys.maxsize
        Heap = []
        for j in range(len(points)):
            x_j, y_j = points[j][0], points[j][1]

            while len(Heap) > 0 and x_j - Heap[0][1] > k:
                heapq.heappop(Heap)

            if len(Heap) > 0:
                target = x_j + y_j - Heap[0][0]
                res = max(target, res)

            heapq.heappush(Heap, (x_j - y_j, x_j))

        return res

Method 2: use priority queue

class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:

        #TC: O(n)
        #SC: worst O(n)

        #keep a monotonely decreasing queue

        res = -sys.maxsize
        Q = collections.deque([])

        for j in range(len(points)):
            x_j, y_j = points[j][0], points[j][1]

            while len(Q) > 0 and x_j - Q[0][1] > k:
                Q.popleft()

            if len(Q) > 0:
                res = max(res, x_j + y_j + Q[0][0])

            while len(Q) > 0 and y_j - x_j >= Q[-1][0]:
                Q.pop()

            Q.append((y_j - x_j, x_j))

        return res