2023年7月21日每日一题--1499. 满足不等式的最大值

leetcode链接：
https://leetcode.cn/problems/max-value-of-equation/

题目分析

方法一：尝试暴力求解，超出时间限制，时间复杂度过高

方法二：尝试通过空间换时间
https://leetcode.cn/problems/max-value-of-equation/solution/man-zu-bu-deng-shi-de-zui-da-zhi-by-leet-5rbj/
根据官方题解写出此题答案

方案一：暴力求解

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int result = Integer.MIN_VALUE;
        int left = 0, right = 1;

        for (; left < points.length; right++) {
            if (right < points.length && Math.abs(points[left][0] - points[right][0]) <= k) {
                if (result < Math.abs(points[left][0] - points[right][0]) + points[left][1] + points[right][1]) {
                    result = Math.abs(points[left][0] - points[right][0]) + points[left][1] + points[right][1];
                }

            } else {
                left++;
                right = left;
            }
        }
        
        return result;
    }
}

结果

超出时间限制
63 / 66 个通过测试用例

分析

时间复杂度：
O( n ^ 2 )

空间复杂度：
O( 1 )

方案二

https://leetcode.cn/problems/max-value-of-equation/solution/man-zu-bu-deng-shi-de-zui-da-zhi-by-leet-5rbj/
https://leetcode.cn/problems/max-value-of-equation/solution/on-dan-diao-dui-lie-fu-ti-dan-pythonjava-hhrr/
官方题解
警示：遇到算法题中的数学公式，一定要敏感，查看一下其是否可以正常化简！！！

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int result = Integer.MIN_VALUE;
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((o1, o2) -> (o1[0] - o2[0]));

        for (int[] point : points) {
            while (!priorityQueue.isEmpty() && point[0] - priorityQueue.peek()[1] > k) {
                priorityQueue.poll();
            }
            if (!priorityQueue.isEmpty()) {
                result = Math.max(result, point[0] + point[1] - priorityQueue.peek()[0]);
            }
            priorityQueue.offer(new int[]{point[0] - point[1], point[0]});
        }

        return result;
    }
}

结果

解答成功:
执行耗时:16 ms,击败了76.60% 的Java用户
内存消耗:103.5 MB,击败了19.15% 的Java用户

分析

时间复杂度：
O( n * logn )

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/max-value-of-equation/solution/man-zu-bu-deng-shi-de-zui-da-zhi-by-leet-5rbj/

方法一：堆

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int res = Integer.MIN_VALUE;
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        for (int[] point : points) {
            int x = point[0], y = point[1];
            while (!heap.isEmpty() && x - heap.peek()[1] > k) {
                heap.poll();
            }
            if (!heap.isEmpty()) {
                res = Math.max(res, x + y - heap.peek()[0]);
            }
            heap.offer(new int[]{x - y, x});
        }
        return res;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/max-value-of-equation/solution/man-zu-bu-deng-shi-de-zui-da-zhi-by-leet-5rbj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：双端队列

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/max-value-of-equation/solution/man-zu-bu-deng-shi-de-zui-da-zhi-by-leet-5rbj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。