Max Value of Equation Solutions in C++

/// Source : https://leetcode.com/problems/max-value-of-equation/
/// Author : liuyubobobo
/// Time   : 2020-06-28

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


/// Using Priority Queue
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

        priority_queue<pair<int, int>> pq;

        // 初始放入第一个点的信息
        pq.push({points[0][1] - points[0][0], points[0][0]});

        int res = INT_MIN;
        for(int i = 1; i < points.size(); i ++){
            // 将优先队列队头不符合条件的点扔掉
            while(!pq.empty() && points[i][0] - pq.top().second > k) pq.pop();

            // 使用优先队列队首元素信息更新解
            if(!pq.empty())
                res = max(res, points[i][1] + points[i][0] + pq.top().first);

            // 将当前点的信息放入优先队列
            pq.push({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};


int main() {

    vector<vector<int>> points1 = {{1,3},{2,0},{5,10},{6,-10}};
    cout << Solution().findMaxValueOfEquation(points1, 1) << endl;
    // 4

    vector<vector<int>> points2 = {{0,0},{3,0},{9,2}};
    cout << Solution().findMaxValueOfEquation(points2, 3) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/max-value-of-equation/
/// Author : liuyubobobo
/// Time   : 2020-06-28

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Using BST
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

        set<pair<int, int>> tree;

        // 初始放入第一个点的信息
        tree.insert({points[0][1] - points[0][0], points[0][0]});

        int res = INT_MIN, j = 0;
        for(int i = 1; i < points.size(); i ++){

            // 删除红黑树中不满足条件的数据
            while(j < i && points[i][0] - points[j][0] > k){
                tree.erase({points[j][1] - points[j][0], points[j][0]});
                j ++;
            }

            // 使用红黑树最大元素信息更新解
            if(!tree.empty())
                res = max(res, points[i][1] + points[i][0] + tree.rbegin()->first);

            // 将当前点的信息放入红黑树
            tree.insert({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};


int main() {

    vector<vector<int>> points1 = {{1,3},{2,0},{5,10},{6,-10}};
    cout << Solution().findMaxValueOfEquation(points1, 1) << endl;
    // 4

    vector<vector<int>> points2 = {{0,0},{3,0},{9,2}};
    cout << Solution().findMaxValueOfEquation(points2, 3) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/max-value-of-equation/
/// Author : liuyubobobo
/// Time   : 2020-06-28

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Using BST 2
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

        set<pair<int, int>> tree;

        // 初始放入第一个点的信息
        tree.insert({points[0][1] - points[0][0], points[0][0]});

        int res = INT_MIN;
        for(int i = 1; i < points.size(); i ++){

            // 取出红黑树中的最大 y - x 值，如果不满足约束，则删除
            while(!tree.empty() && points[i][0] - tree.rbegin()->second > k)
                tree.erase(--tree.end());

            // 使用红黑树最大元素信息更新解
            if(!tree.empty())
                res = max(res, points[i][1] + points[i][0] + tree.rbegin()->first);

            // 将当前点的信息放入红黑树
            tree.insert({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};


int main() {

    vector<vector<int>> points1 = {{1,3},{2,0},{5,10},{6,-10}};
    cout << Solution().findMaxValueOfEquation(points1, 1) << endl;
    // 4

    vector<vector<int>> points2 = {{0,0},{3,0},{9,2}};
    cout << Solution().findMaxValueOfEquation(points2, 3) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/max-value-of-equation/
/// Author : liuyubobobo
/// Time   : 2020-06-28

#include <iostream>
#include <vector>
#include <deque>

using namespace std;


/// Using Mono Queue
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

        deque<pair<int, int>> dq;

        // 初始放入第一个点的信息
        dq.push_front({points[0][1] - points[0][0], points[0][0]});

        int res = INT_MIN;
        for(int i = 1; i < points.size(); i ++){

            // 对队列首不符合约束的点删除
            while(!dq.empty() && points[i][0] - dq.front().second > k)
                dq.pop_front();

            // 根据队首最大元素信息更新解
            if(!dq.empty())
                res = max(res, points[i][1] + points[i][0] + dq.front().first);

            // 把队列尾的比当前 y - x 还小的元素删除
            while(!dq.empty() && dq.back().first <= points[i][1] - points[i][0])
                dq.pop_back();

            // 将当前点的信息加入队列
            dq.push_back({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};


int main() {

    vector<vector<int>> points1 = {{1,3},{2,0},{5,10},{6,-10}};
    cout << Solution().findMaxValueOfEquation(points1, 1) << endl;
    // 4

    vector<vector<int>> points2 = {{0,0},{3,0},{9,2}};
    cout << Solution().findMaxValueOfEquation(points2, 3) << endl;
    // 3

    return 0;
}