{"id":8403,"date":"2021-04-25T15:30:06","date_gmt":"2021-04-25T22:30:06","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8403"},"modified":"2021-04-25T15:30:20","modified_gmt":"2021-04-25T22:30:20","slug":"leetcode-1840-maximum-building-height","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1840-maximum-building-height\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1840. Maximum Building Height"},"content":{"rendered":"\n<p>You want to build&nbsp;<code>n<\/code>&nbsp;new buildings in a city. The new buildings will be built in a line and are labeled from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>.<\/p>\n\n\n\n<p>However, there are city restrictions on the heights of the new buildings:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The height of each building must be a non-negative integer.<\/li><li>The height of the first building&nbsp;<strong>must<\/strong>&nbsp;be&nbsp;<code>0<\/code>.<\/li><li>The height difference between any two adjacent buildings&nbsp;<strong>cannot exceed<\/strong>&nbsp;<code>1<\/code>.<\/li><\/ul>\n\n\n\n<p>Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array&nbsp;<code>restrictions<\/code>&nbsp;where&nbsp;<code>restrictions[i] = [id<sub>i<\/sub>, maxHeight<sub>i<\/sub>]<\/code>&nbsp;indicates that building&nbsp;<code>id<sub>i<\/sub><\/code>&nbsp;must have a height&nbsp;<strong>less than or equal to<\/strong>&nbsp;<code>maxHeight<sub>i<\/sub><\/code>.<\/p>\n\n\n\n<p>It is guaranteed that each building will appear&nbsp;<strong>at most once<\/strong>&nbsp;in&nbsp;<code>restrictions<\/code>, and building&nbsp;<code>1<\/code>&nbsp;will&nbsp;<strong>not<\/strong>&nbsp;be in&nbsp;<code>restrictions<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>maximum possible height<\/strong>&nbsp;of the&nbsp;<strong>tallest<\/strong>&nbsp;building<\/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\/2021\/04\/08\/ic236-q4-ex1-1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 5, restrictions = [[2,1],[4,1]]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> The green area in the image indicates the maximum allowed height for each building.\nWe can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/04\/08\/ic236-q4-ex2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 6, restrictions = []\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong> The green area in the image indicates the maximum allowed height for each building.\nWe can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/04\/08\/ic236-q4-ex3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong> The green area in the image indicates the maximum allowed height for each building.\nWe can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= n &lt;= 10<sup>9<\/sup><\/code><\/li><li><code>0 &lt;= restrictions.length &lt;= min(n - 1, 10<sup>5<\/sup>)<\/code><\/li><li><code>2 &lt;= id<sub>i<\/sub>&nbsp;&lt;= n<\/code><\/li><li><code>id<sub>i<\/sub><\/code>&nbsp;is&nbsp;<strong>unique<\/strong>.<\/li><li><code>0 &lt;= maxHeight<sub>i<\/sub>&nbsp;&lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Two Passes<\/strong><\/h2>\n\n\n\n<p>Trim the max heights based on neighboring max heights.<br>Two passes: left to right, right to left.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/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 maxBuilding(int n, vector<vector<int>>& rs) {\n    rs.push_back({1, 0});\n    sort(begin(rs), end(rs));\n    if (rs.back()[0] != n)\n      rs.push_back({n, n - 1});\n    \n    const int m = rs.size();\n    for (int i = 1; i < m; ++i)\n      rs[i][1] = min(rs[i][1], rs[i - 1][1] + rs[i][0] - rs[i - 1][0]);\n    for (int i = m - 2; i >= 0; --i)\n      rs[i][1] = min(rs[i][1], rs[i + 1][1] - rs[i][0] + rs[i + 1][0]);\n    \n    int ans = 0;\n    for (int i = 1; i < m; ++i) {\n      const int l = rs[i - 1][1];\n      const int r = rs[i][1];\n      ans = max(ans, max(l, r) + (rs[i][0] - rs[i - 1][0] - abs(l - r)) \/ 2);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You want to build&nbsp;n&nbsp;new buildings in a city. The new buildings will be built in a line and are labeled from&nbsp;1&nbsp;to&nbsp;n. However, there are city&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,217,709],"class_list":["post-8403","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-hard","tag-two-passes","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8403","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=8403"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8403\/revisions"}],"predecessor-version":[{"id":8405,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8403\/revisions\/8405"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}