{"id":7598,"date":"2020-11-01T09:36:27","date_gmt":"2020-11-01T17:36:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7598"},"modified":"2020-11-01T11:17:19","modified_gmt":"2020-11-01T19:17:19","slug":"leetcode-1642-furthest-building-you-can-reach","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/heap\/leetcode-1642-furthest-building-you-can-reach\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1642. Furthest Building You Can Reach"},"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 1642. Furthest Building You Can Reach - \u5237\u9898\u627e\u5de5\u4f5c EP366\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/FowBaF5hYcY?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>You are given an integer array&nbsp;<code>heights<\/code>&nbsp;representing the heights of buildings, some&nbsp;<code>bricks<\/code>, and some&nbsp;<code>ladders<\/code>.<\/p>\n\n\n\n<p>You start your journey from building&nbsp;<code>0<\/code>&nbsp;and move to the next building by possibly using bricks or ladders.<\/p>\n\n\n\n<p>While moving from building&nbsp;<code>i<\/code>&nbsp;to building&nbsp;<code>i+1<\/code>&nbsp;(<strong>0-indexed<\/strong>),<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If the current building&#8217;s height is&nbsp;<strong>greater than or equal<\/strong>&nbsp;to the next building&#8217;s height, you do&nbsp;<strong>not<\/strong>&nbsp;need a ladder or bricks.<\/li><li>If the current building&#8217;s height is&nbsp;<strong>less than<\/strong>&nbsp;the next building&#8217;s height, you can either use&nbsp;<strong>one ladder<\/strong>&nbsp;or&nbsp;<code>(h[i+1] - h[i])<\/code>&nbsp;<strong>bricks<\/strong>.<\/li><\/ul>\n\n\n\n<p><em>Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/10\/27\/q4.gif\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> Starting at building 0, you can follow these steps:\n- Go to building 1 without using ladders nor bricks since 4 &gt;= 2.\n- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 &lt; 7.\n- Go to building 3 without using ladders nor bricks since 7 &gt;= 6.\n- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 &lt; 9.\nIt is impossible to go beyond building 4 because you do not have any more bricks or ladders.\n<\/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> heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2\n<strong>Output:<\/strong> 7\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> heights = [14,3,19,3], bricks = 17, ladders = 0\n<strong>Output:<\/strong> 3\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= heights.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= heights[i] &lt;= 10<sup>6<\/sup><\/code><\/li><li><code>0 &lt;= bricks &lt;= 10<sup>9<\/sup><\/code><\/li><li><code>0 &lt;= ladders &lt;= heights.length<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 0: DFS<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-1.png\" alt=\"\" class=\"wp-image-7602\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(2^n)<br>Space complexity: O(n)<\/p>\n\n\n\n<p>AC but should be TLE<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Binary Search + Greedy<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-2.png\" alt=\"\" class=\"wp-image-7601\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Guess we can reach to m, sort the height differences from 0~m. Use ladders for larger values and use bricks for smallest values left.<\/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, 300 ms\nclass Solution {\npublic:\n  int furthestBuilding(vector<int>& heights, int bricks, int ladders) {\n    const int n = heights.size();\n    if (ladders >= n - 1) return n - 1;\n    vector<int>  diffs(n);\n    for (int i = 1; i < n; ++i)\n      diffs[i - 1] = max(0, heights[i] - heights[i - 1]);\n    int l = ladders;\n    int r = n;\n    while (l < r) {\n      int m = l + (r - l) \/ 2;\n      vector<int> d(begin(diffs), begin(diffs) + m);\n      nth_element(begin(d), end(d) - ladders, end(d));\n      if (accumulate(begin(d), end(d) - ladders, 0) > bricks)\n        r = m;\n      else\n        l = m + 1;\n    }\n    return l - 1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Min heap<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-3.png\" alt=\"\" class=\"wp-image-7603\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1642-ep366-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Use a min heap to store all the height differences ( &gt; 0) so far, if heap size is greater than ladders, which means we have to use bricks, extract the smallest value and subtract the bricks.<\/p>\n\n\n\n<p>Time complexity: O(nlogk)<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, 216 ms\nclass Solution {\npublic:\n  int furthestBuilding(vector<int>& heights, int bricks, int ladders) {\n    const int n = heights.size();        \n    priority_queue<int, vector<int>, greater<int>> q;\n    for (int i = 1; i < n; ++i) {\n      const int d = heights[i] - heights[i - 1];\n      if (d <= 0) continue;\n      q.push(d);\n      if (q.size() <= ladders) continue;\n      bricks -= q.top(); q.pop();\n      if (bricks < 0) return i - 1;      \n    }\n    return n - 1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;heights&nbsp;representing the heights of buildings, some&nbsp;bricks, and some&nbsp;ladders. You start your journey from building&nbsp;0&nbsp;and move to the next building by&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71],"tags":[52,88,73,15],"class_list":["post-7598","post","type-post","status-publish","format-standard","hentry","category-heap","tag-binary-search","tag-greedy","tag-heap","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7598","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=7598"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7598\/revisions"}],"predecessor-version":[{"id":7604,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7598\/revisions\/7604"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7598"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}