X

LEETCODE 1499. 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 是严格递增的。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1499

解题思路分析:

我们首先看下题目给出的公式:

sum = yi + yj + |xi - xj|;

因为xj一定大于xi,因此公式可以变形为:

sum = yi + yj + (xj - xi);

继续变形可得:

sum = (yi - xi) + (yj + xj);

上面的公式我们可以理解为两个部分,前半部分是一个点的纵坐标减去横坐标,后半部分是一个点的纵坐标加上横坐标。解题时,我们采取滑动窗口(双指针)方式来解题,初始时,左指针位于数组下标为0处,右指针位于下标为1处。此时如果右指针横坐标与左指针横坐标之差大于k,那么我们需要向右移动一位左指针来缩小两者之间的差值。注意如果移动后左右指针位于同一位置的话,由于区间内至少要保证拥有2个元素,所以右指针也需向右侧移动一位。

反之,如果右指针横坐标与左指针横坐标之差小于等于k,此时右指针代表当前点,我们计算出当前点横坐标与纵坐标之和(yj + xj)。然后再在[left, right)区间,即右指针到左指针下标减一范围内找到一个最大的(yi – xi),这两者的和即是当前区间内最大sum。并使用该sum更新全局最大sum。然后右指针向右移动一格后继续重复上述步骤,直到右指针越界为止。

这样问题就剩下如何在一个区间内快速找到一个最大值(yi – xi)。关于这个问题,我们在之前的文章中介绍过:LEETCODE 239. Sliding Window Maximum 解题思路分析。最简单的方式是采用一个双向队列,使用递减方式保存区间内的值,此时队列头部的元素一定是区间内最大值。详细解法可以参考leetcode 239这道题目。

实现代码:

public int findMaxValueOfEquation(int[][] points, int k) {
    // 返回结果
    int res=Integer.MIN_VALUE;
    // 左右指针
    int left=0,right=1;
    // 用于保存区间内最大值的queue
    Deque<Integer> dq = new LinkedList<>();
    // 将[left, right)区间内元素加入到queue
    dq.offerLast(points[0][1]-points[0][0]);
    while(right<points.length){
        if(points[right][0]-points[left][0]>k){ // 两点的x坐标差大于k
            // 将左指针指向元素移除区间
            // 如果queue中的最大值等于左指针指向点的纵横坐标差,
            if(dq.size()>0&&points[left][1]-points[left][0]==dq.peekFirst()){
                dq.pollFirst(); // 将最大值移除queue
            }
            left++; // 左指针加一
            if(right==left){ // 如果左右指针相同
                dq.clear(); // 清空queue
                // 将[left, right)区间内元素加入到queue
                dq.offerLast(points[left][1]-points[left][0]);
                right++; // 右指针加一
            }
        }else{ // 两点的x坐标差小于等于k
            // 计算当前sum:queue中最大值加上当前点横纵坐标和
            int sum=dq.peekFirst()+(points[right][1]+points[right][0]);
            res=Math.max(res,sum); // 更新全局最大值
            // 将当前元素加入Queue,
            // 加入之前,先poll出所有小于当前元素的值
            while(dq.size()>0&&points[right][1]-points[right][0]>dq.peekLast()){
                dq.pollLast();
            }
            // 将当前元素加入Queue,
            dq.offerLast(points[right][1]-points[right][0]);
            right++;  // 右指针加一
        }
    }
    return res;
}

本题解法执行时间为16ms。

Runtime: 16 ms, faster than 66.43% of Java online submissions for Max Value of Equation.

Memory Usage: 86.3 MB, less than 100.00% of Java online submissions for Max Value of Equation.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1499-max-value-of-equation-解题思路分析/
Categories: leetcode
kwantong: