{"id":7011,"date":"2020-06-28T15:07:06","date_gmt":"2020-06-28T22:07:06","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7011"},"modified":"2020-07-08T17:59:18","modified_gmt":"2020-07-09T00:59:18","slug":"leetcode-1499-max-value-of-equation","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/queue\/leetcode-1499-max-value-of-equation\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1499. Max Value of Equation"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1499. Max Value of Equation - \u5237\u9898\u627e\u5de5\u4f5c EP340\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/GahRKbpoQVQ?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given an&nbsp;array&nbsp;<code>points<\/code>&nbsp;containing the coordinates of points on a 2D plane,&nbsp;sorted by the x-values, where&nbsp;<code>points[i] = [x<sub>i<\/sub>, y<sub>i<\/sub>]<\/code>&nbsp;such that&nbsp;<code>x<sub>i<\/sub>&nbsp;&lt; x<sub>j<\/sub><\/code>&nbsp;for all&nbsp;<code>1 &lt;= i &lt; j &lt;= points.length<\/code>. You are also given an integer&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p>Find the&nbsp;<em>maximum value of the equation&nbsp;<\/em><code>y<sub>i<\/sub>&nbsp;+ y<sub>j<\/sub>&nbsp;+ |x<sub>i<\/sub>&nbsp;- x<sub>j<\/sub>|<\/code>&nbsp;where&nbsp;<code>|x<sub>i<\/sub>&nbsp;- x<sub>j<\/sub>|&nbsp;&lt;= k<\/code>&nbsp;and&nbsp;<code>1 &lt;= i &lt; j &lt;= points.length<\/code>. It is guaranteed that there exists at least one pair of points that satisfy the constraint&nbsp;<code>|x<sub>i<\/sub>&nbsp;- x<sub>j<\/sub>|&nbsp;&lt;= k<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> points = [[1,3],[2,0],[5,10],[6,-10]], k = 1\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> The first two points satisfy the condition |x<sub>i<\/sub>&nbsp;- x<sub>j<\/sub>| &lt;= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1.\nNo other pairs satisfy the condition, so we return the max of 4 and 1.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> points = [[0,0],[3,0],[9,2]], k = 3\n<strong>Output:<\/strong> 3\n<strong>Explanation: <\/strong>Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= points.length &lt;= 10^5<\/code><\/li><li><code>points[i].length == 2<\/code><\/li><li><code>-10^8&nbsp;&lt;= points[i][0], points[i][1] &lt;= 10^8<\/code><\/li><li><code>0 &lt;= k &lt;= 2 * 10^8<\/code><\/li><li><code>points[i][0] &lt; points[j][0]<\/code>&nbsp;for all&nbsp;<code>1 &lt;= i &lt; j &lt;= points.length<\/code><\/li><li><code>x<sub>i<\/sub><\/code>&nbsp;form a strictly increasing sequence.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Observation<\/strong><\/h2>\n\n\n\n<p>Since xj &gt; xi, so |xi &#8211; xj| + yi + yj =&gt; xj + yj + (yi &#8211; xi)<br>We want to have yi &#8211; xi as large as possible while need to make sure xj &#8211; xi &lt;= k.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Priority Queue \/ Heap<\/strong><\/h2>\n\n\n\n<p>Put all the points processed so far onto the heap as (y-x, x) sorted by y-x in descending order.<br>Each new point (x_j, y_j), find the largest y-x such that x_j &#8211; x &lt;= k.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findMaxValueOfEquation(vector<vector<int>>& points, int k) {\n    priority_queue<pair<int, int>> q; \/\/ {y - x, x}    \n    q.emplace(0, -1e9);\n    int ans = INT_MIN;\n    for (const auto& p : points) {\n      const int x = p[0], y = p[1];\n      while (!q.empty() && x - q.top().second > k) q.pop();\n      if (!q.empty())\n        ans = max(ans, x + y + q.top().first);\n      q.emplace(y - x, x);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Monotonic Queue<\/strong><\/h2>\n\n\n\n<p><br>Maintain a monotonic queue:<br>1. The queue is sorted by y &#8211; x in descending order. <br>2. Pop then front element when xj &#8211; x_front &gt; k, they can&#8217;t be used anymore.<br>3. Record the max of {xj + yj + (y_front &#8211; x_front)}<br>4. Pop the back element when yj &#8211; xj &gt; y_back &#8211; x_back, they are smaller and lefter. Won&#8217;t be useful anymore.<br>5. Finally, push the j-th element onto the queue.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findMaxValueOfEquation(vector<vector<int>>& points, int k) {    \n    deque<pair<int, int>> q; \/\/ {y - x, x} Sort by y - x.\n    int ans = INT_MIN;\n    for (const auto& p : points) {\n      const int xj = p[0];\n      const int yj = p[1];\n      \/\/ Remove invalid points, e.g. xj - xi > k\n      while (!q.empty() && xj - q.front().second > k)\n        q.pop_front();\n      if (!q.empty())\n        ans = max(ans, xj + yj + q.front().first);      \n      while (!q.empty() && yj - xj >= q.back().first) \n        q.pop_back();\n      q.emplace_back(yj - xj, xj);\n    }\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass Solution {\n  public int findMaxValueOfEquation(int[][] points, int k) {\n    var q = new ArrayDeque<Integer>();\n    int ans = Integer.MIN_VALUE;\n    for (int i = 0; i < points.length; ++i) {\n      int xj = points[i][0];\n      int yj = points[i][1];\n      \n      while (!q.isEmpty() &#038;&#038; xj - points[q.getFirst()][0] > k) {\n        q.removeFirst();\n      }\n      \n      if (!q.isEmpty()) {\n        ans = Math.max(ans, xj + yj \n                + points[q.getFirst()][1] - points[q.getFirst()][0]);\n      }\n      \n      while (!q.isEmpty() && yj - xj \n                >= points[q.getLast()][1] - points[q.getLast()][0]) {\n        q.removeLast();\n      }\n      \n      q.offer(i);\n    }\n    return ans;\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n# Author: Huahua\nclass Solution:\n  def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n    ans = float('-inf')\n    q = deque() # {(y - x, x)}\n    for x, y in points:\n      while q and x - q[0][1] > k: q.popleft()\n      if q: ans = max(ans, x + y + q[0][0])\n      while q and y - x >= q[-1][0]: q.pop()\n      q.append((y - x, x))\n    return ans\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an&nbsp;array&nbsp;points&nbsp;containing the coordinates of points on a 2D plane,&nbsp;sorted by the x-values, where&nbsp;points[i] = [xi, yi]&nbsp;such that&nbsp;xi&nbsp;&lt; xj&nbsp;for all&nbsp;1 &lt;= i &lt; j &lt;=&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[429],"tags":[217,587],"class_list":["post-7011","post","type-post","status-publish","format-standard","hentry","category-queue","tag-hard","tag-monotonic-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7011","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7011"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7011\/revisions"}],"predecessor-version":[{"id":7055,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7011\/revisions\/7055"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}