[数据结构与算法]1499. 满足不等式的最大值 详解

1499. 满足不等式的最大值

给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 $points[i]=[x_i,y_i]$ ，并且在 $1<=i<j<=points.length$ 的前提下， $x_i<x_j$ 总成立。

请你找出 $y_i+y_j+|x_i?x_j|$ 的 最大值，其中 $|xi?xj|<=k$ 且 $1<=i<j<=points.length$。

题目测试数据保证至少存在一对能够满足 $|x_i?x_j|<=k$的点。

捕捉题干信息我们发现：

• 在 $1<=i<j<=points.length$ 的前提下， $x_i<x_j$ 总成立。 ①
• 找出 $y_i+y_j+|x_i?x_j|$ 的 最大值，其中 $|x_i?x_j|\le k$ 且 $1\le i<j\le points.length$。 ②

以①为条件可对②进行化简：

• $y_i+y_j+|x_i?x_j|$—>$(y_i?x_i)+(y_j+x_j)$
• $|x_i?x_j|\le k$ —>$x_j?x_i\le k$

由此我们使用pair<T₁, T₂>(当pair为堆元素时，默认使用first元素为基准进行排序) 分别存放：

• T1 = $y_i?x_i$

• T2 = $x_j?x_i$

正如我们所说，pair作为元素时以第一个元素为基准默认进行大根堆排序(降序)

因此我们每次进行$|x_i?x_j|\le k$ （k值）的合理性判断+$y_i+y_j+|x_i?x_j|$最大值动态更新即可

代码如下：

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, int>> q;
        q.push({points[0][1]-points[0][0], points[0][0]});
        // 首先先将第一个数传入，防止队列为空
        int ans = INT_MIN;   // 把答案假定为 整型最小值 方便后期比较
        for(int i = 1; i < points.size(); ++i) {
            while(!q.empty()&&points[i][0]-q.top().second > k) {  
            // 如果队列不为空 且合理性不通过，弹出当前与之比较的数据即可，直到合理为止
                q.pop();
            }
            if(!q.empty()) {  // 如果不为空动态更新答案即可
                ans = max(ans, q.top().first + points[i][0]+points[i][1]);
            }
            q.push({points[i][1]-points[i][0], points[i][0]});
        }        
        return ans;
    }
};