{"id":693,"date":"2017-10-24T20:09:00","date_gmt":"2017-10-25T03:09:00","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=693"},"modified":"2018-04-19T08:33:43","modified_gmt":"2018-04-19T15:33:43","slug":"leetcode-699-falling-squares","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-699-falling-squares\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 699. Falling Squares"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 699. Falling Squares - \u5237\u9898\u627e\u5de5\u4f5c EP97\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/UeuV-6Ygxs4?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><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u65b9\u5757\u843d\u4e0b\u540e\u4f1a\u5806\u53e0\u5728\u91cd\u53e0\u7684\u65b9\u5757\u4e4b\u4e0a\uff0c\u95ee\u6bcf\u4e00\u5757\u65b9\u5757\u843d\u4e0b\u4e4b\u540e\u6700\u9ad8\u7684\u65b9\u5757\u7684\u9ad8\u5ea6\u662f\u591a\u5c11\uff1f<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>On an infinite number line (x-axis), we drop given squares in the order they are given.<\/p>\n<p>The\u00a0<code>i<\/code>-th square dropped (<code>positions[i] = (left, side_length)<\/code>) is a square with the left-most point being\u00a0<code>positions[i][0]<\/code>\u00a0and sidelength\u00a0<code>positions[i][1]<\/code>.<\/p>\n<p>The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.<\/p>\n<p>The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.<\/p>\n<p>&nbsp;<\/p>\n<p>Return a list\u00a0<code>ans<\/code>\u00a0of heights. Each height\u00a0<code>ans[i]<\/code>\u00a0represents the current highest height of any square we have dropped, after dropping squares represented by\u00a0<code>positions[0], positions[1], ..., positions[i]<\/code>.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"lang:default decode:true\">Input: [[1, 2], [2, 3], [6, 1]]\r\nOutput: [2, 5, 5]\r\nExplanation:\r\n\r\nAfter the first drop of \r\npositions[0] = [1, 2]:\r\n_aa\r\n_aa\r\n-------\r\nThe maximum height of any square is 2.\r\n\r\n\r\nAfter the second drop of \r\npositions[1] = [2, 3]:\r\n__aaa\r\n__aaa\r\n__aaa\r\n_aa__\r\n_aa__\r\n--------------\r\nThe maximum height of any square is 5.  \r\nThe larger square stays on top of the smaller square despite where its center\r\nof gravity is, because squares are infinitely sticky on their bottom edge.\r\n\r\n\r\nAfter the third drop of \r\npositions[1] = [6, 1]:\r\n__aaa\r\n__aaa\r\n__aaa\r\n_aa\r\n_aa___a\r\n--------------\r\nThe maximum height of any square is still 5.\r\n\r\nThus, we return an answer of \r\n[2, 5, 5]\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"\">Input: [[100, 100], [200, 100]]\r\nOutput: [100, 100]\r\nExplanation: Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li><code>1 &lt;= positions.length &lt;= 1000<\/code>.<\/li>\n<li><code>1 &lt;= positions[i][0] &lt;= 10^8<\/code>.<\/li>\n<li><code>1 &lt;= positions[i][1] &lt;= 10^6<\/code>.<\/li>\n<\/ul>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Range query with map<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-701\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-700\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/699-ep97-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++ map<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 29 ms\r\nclass Solution {\r\npublic:\r\n    vector&lt;int&gt; fallingSquares(vector&lt;pair&lt;int, int&gt;&gt;&amp; positions) {\r\n        vector&lt;int&gt; ans;\r\n        map&lt;pair&lt;int, int&gt;, int&gt; b; \/\/ {{start, end}, height}        \r\n        int maxHeight = INT_MIN;\r\n        for (const auto&amp; kv: positions) {\r\n            int start = kv.first;\r\n            int size = kv.second;\r\n            int end = start + size;\r\n            \/\/ first range intersect with new_interval\r\n            auto it = b.upper_bound({start, end});\r\n            if (it != b.begin()) {\r\n                auto it2 = it;\r\n                if ((--it2)-&gt;first.second &gt; start) it = it2;\r\n            }\r\n            \r\n            int baseHeight = 0;\r\n            vector&lt;tuple&lt;int, int, int&gt;&gt; ranges;\r\n            while (it != b.end() &amp;&amp; it-&gt;first.first &lt; end) {\r\n                const int s = it-&gt;first.first;\r\n                const int e = it-&gt;first.second;\r\n                const int h = it-&gt;second;\r\n                if (s &lt; start) ranges.emplace_back(s, start, h);\r\n                if (e &gt; end) ranges.emplace_back(end, e, h);\r\n                \/\/ max height of intesected ranges\r\n                baseHeight = max(baseHeight, h);\r\n                it = b.erase(it);\r\n            }\r\n            \r\n            int newHeight = size + baseHeight;\r\n            \r\n            b[{start, end}] = newHeight;\r\n            \r\n            for (const auto&amp; range: ranges)\r\n                b[{get&lt;0&gt;(range), get&lt;1&gt;(range)}] = get&lt;2&gt;(range);\r\n            \r\n            maxHeight = max(maxHeight, newHeight);            \r\n            ans.push_back(maxHeight);\r\n        }\r\n        return ans;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ vector without merge<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 46 ms\r\nclass Solution {\r\npublic:\r\n    vector&lt;int&gt; fallingSquares(vector&lt;pair&lt;int, int&gt;&gt;&amp; positions) {\r\n        vector&lt;int&gt; ans;\r\n        vector&lt;Interval&gt; intervals;\r\n        int maxHeight = INT_MIN;\r\n        for (const auto&amp; kv: positions) {\r\n            int start = kv.first;\r\n            int end = start + kv.second;            \r\n            int baseHeight = 0;\r\n            for (const Interval&amp; interval : intervals) {\r\n                if (interval.start &gt;= end || interval.end &lt;= start)             \r\n                    continue;\r\n                baseHeight = max(baseHeight, interval.height);\r\n            }\r\n            int height = kv.second + baseHeight;\r\n            intervals.push_back(Interval(start, end, height));\r\n            maxHeight = max(maxHeight, height);\r\n            ans.push_back(maxHeight);\r\n        }\r\n        return ans;\r\n    }\r\nprivate:\r\n    struct Interval {\r\n        int start;\r\n        int end;\r\n        int height;\r\n        Interval(int start, int end, int height) \r\n            : start(start), end(end), height(height) {}\r\n    };\r\n};<\/pre>\n<p>C++ \/ vector with merge (slower)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 86 ms\r\nclass Solution {\r\npublic:\r\n    vector&lt;int&gt; fallingSquares(vector&lt;pair&lt;int, int&gt;&gt;&amp; positions) {\r\n        vector&lt;int&gt; ans;\r\n        vector&lt;Interval&gt; intervals;\r\n        int maxHeight = INT_MIN;\r\n        for (const auto&amp; kv: positions) {\r\n            vector&lt;Interval&gt; tmp;\r\n            int start = kv.first;\r\n            int end = start + kv.second;            \r\n            int baseHeight = 0;\r\n            for (const Interval&amp; interval : intervals) {\r\n                if (interval.start &gt;= end || interval.end &lt;= start) {\r\n                    tmp.push_back(interval);                \r\n                    continue;\r\n                }\r\n                baseHeight = max(baseHeight, interval.height);\r\n                if (interval.start &lt; start || interval.end &gt; end)\r\n                    tmp.push_back(interval);\r\n            }\r\n            int height = kv.second + baseHeight;\r\n            tmp.push_back(Interval(start, end, height));\r\n            intervals.swap(tmp);\r\n            maxHeight = max(maxHeight, height);\r\n            ans.push_back(maxHeight);\r\n        }\r\n        return ans;\r\n    }\r\nprivate:\r\n    struct Interval {\r\n        int start;\r\n        int end;\r\n        int height;\r\n        Interval(int start, int end, int height) \r\n            : start(start), end(end), height(height) {}\r\n    };\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-715-range-module\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 715. Range Module<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-218-the-skyline-problem\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 218. The Skyline Problem<\/a><\/li>\n<li>[\u89e3\u9898\u62a5\u544a] LeetCode 57. Insert Interval<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u65b9\u5757\u843d\u4e0b\u540e\u4f1a\u5806\u53e0\u5728\u91cd\u53e0\u7684\u65b9\u5757\u4e4b\u4e0a\uff0c\u95ee\u6bcf\u4e00\u5757\u65b9\u5757\u843d\u4e0b\u4e4b\u540e\u6700\u9ad8\u7684\u65b9\u5757\u7684\u9ad8\u5ea6\u662f\u591a\u5c11\uff1f Problem: On an infinite number line (x-axis), we drop given squares in the order they are given. The\u00a0i-th square dropped (positions[i] = (left, side_length))&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127,165],"tags":[142,141,139],"class_list":["post-693","post","type-post","status-publish","format-standard","hentry","category-geometry","category-hard","tag-height","tag-max","tag-range","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/693","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=693"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/693\/revisions"}],"predecessor-version":[{"id":2604,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/693\/revisions\/2604"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=693"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=693"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=693"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}