LC.P1499[满足不等式的最大值]

发表于2023-07-21|更新于2023-07-24|LeetCode

|字数总计:125|阅读时长:1分钟|阅读量:

方法一：双端队列

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int ans = Integer.MIN_VALUE;
        // (xi, yi - xi)
        Deque<int[]> q = new ArrayDeque<>();
        for (int[] point : points) {
            int x = point[0], y = point[1];
            while (!q.isEmpty() && q.peekFirst()[0] < x - k) q.pollFirst();
            if (!q.isEmpty()) {
                ans = Math.max(ans, x + y + q.peekFirst()[1]);
            }
            while (!q.isEmpty() && q.peekLast()[1] <= y - x) q.pollLast();
            q.offerLast(new int[]{x, y - x});
        }
        return ans;
    }
}