<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0042. 接雨水 ## 題目地址(42. 接雨水) <https://leetcode-cn.com/problems/trapping-rain-water/> ## 題目描述 ``` <pre class="calibre18">``` 給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖,計算按此排列的柱子,下雨之后能接多少雨水。 ``` ``` ![](https://img.kancloud.cn/f2/ac/f2ace69924552df014e65cafe8bd47b7_412x161.jpg) ``` <pre class="calibre18">``` 上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖,在這種情況下,可以接 6 個單位的雨水(藍色部分表示雨水)。 感謝 Marcos 貢獻此圖。 示例: 輸入: [0,1,0,2,1,0,1,3,2,1,2,1] 輸出: 6 ``` ``` ## 前置知識 - 空間換時間 - 雙指針 - 單調棧 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 雙數組 ### 思路 這是一道雨水收集的問題, 難度為`hard`. 如圖所示,讓我們求下過雨之后最多可以積攢多少的水。 如果采用暴力求解的話,思路應該是 height 數組依次求和,然后相加。 偽代碼: ``` <pre class="calibre18">``` <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < height.length; i++) { area += (h[i] - height[i]) * <span class="hljs-params">1</span>; <span class="hljs-title">// h為下雨之后的水位</span> } ``` ``` 問題轉化為求 h,那么 h\[i\]又等于`左右兩側柱子的最大值中的較小值`,即 `h[i] = Math.min(左邊柱子最大值, 右邊柱子最大值)` 如上圖那么 h 為 \[0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1\] 問題的關鍵在于求解`左邊柱子最大值`和`右邊柱子最大值`, 我們其實可以用兩個數組來表示`leftMax`, `rightMax`, 以 leftMax 為例,leftMax\[i\]代表 i 的左側柱子的最大值,因此我們維護兩個數組即可。 ### 關鍵點解析 - 建模 `h[i] = Math.min(左邊柱子最大值, 右邊柱子最大值)`(h 為下雨之后的水位) ### 代碼 代碼支持 JavaScript,Python3,C++: JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=42 lang=javascript * * [42] Trapping Rain Water * */</span> <span class="hljs-title">/** * @param {number[]} height * @return {number} */</span> <span class="hljs-keyword">var</span> trap = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">height</span>) </span>{ <span class="hljs-keyword">let</span> max = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> volume = <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> leftMax = []; <span class="hljs-keyword">const</span> rightMax = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < height.length; i++) { leftMax[i] = max = <span class="hljs-params">Math</span>.max(height[i], max); } max = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = height.length - <span class="hljs-params">1</span>; i >= <span class="hljs-params">0</span>; i--) { rightMax[i] = max = <span class="hljs-params">Math</span>.max(height[i], max); } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < height.length; i++) { volume = volume + <span class="hljs-params">Math</span>.min(leftMax[i], rightMax[i]) - height[i]; } <span class="hljs-keyword">return</span> volume; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trap</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n = len(heights) l, r = [<span class="hljs-params">0</span>] * (n + <span class="hljs-params">1</span>), [<span class="hljs-params">0</span>] * (n + <span class="hljs-params">1</span>) ans = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, len(heights) + <span class="hljs-params">1</span>): l[i] = max(l[i - <span class="hljs-params">1</span>], heights[i - <span class="hljs-params">1</span>]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(heights) - <span class="hljs-params">1</span>, <span class="hljs-params">0</span>, <span class="hljs-params">-1</span>): r[i] = max(r[i + <span class="hljs-params">1</span>], heights[i]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(heights)): ans += max(<span class="hljs-params">0</span>, min(l[i + <span class="hljs-params">1</span>], r[i]) - heights[i]) <span class="hljs-keyword">return</span> ans ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">trap</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& heights)</span> </span>{ <span class="hljs-keyword">if</span>(heights == null) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> ans = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> size = heights.size(); <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>> left_max(size), right_max(size); left_max[<span class="hljs-params">0</span>] = heights[<span class="hljs-params">0</span>]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">1</span>; i < size; i++) { left_max[i] = max(heights[i], left_max[i - <span class="hljs-params">1</span>]); } right_max[size - <span class="hljs-params">1</span>] = heights[size - <span class="hljs-params">1</span>]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = size - <span class="hljs-params">2</span>; i >= <span class="hljs-params">0</span>; i--) { right_max[i] = max(heights[i], right_max[i + <span class="hljs-params">1</span>]); } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">1</span>; i < size - <span class="hljs-params">1</span>; i++) { ans += min(left_max[i], right_max[i]) - heights[i]; } <span class="hljs-keyword">return</span> ans; } ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 雙指針 ### 思路 上面代碼比較好理解,但是需要額外的 N 的空間。從上面解法可以看出,我們實際上只關心左右兩側較小的那一個,并不需要兩者都計算出來。具體來說: - 如果 l\[i + 1\] < r\[i\] 那么 最終積水的高度由 i 的左側最大值決定。 - 如果 l\[i + 1\] >= r\[i\] 那么 最終積水的高度由 i 的右側最大值決定。 因此我們不必維護完整的兩個數組,而是可以只進行一次遍歷,同時維護左側最大值和右側最大值,使用常數變量完成即可。這是一個典型的雙指針問題, 具體算法: 1. 維護兩個指針 left 和 right,分別指向頭尾。 2. 初始化左側和右側最高的高度都為 0。 3. 比較 height\[left\] 和 height\[right\] - 3.1 如果 height\[left\] < height\[right\] - 3.1.1 如果 height\[left\] >= left\_max, 則當前格子積水面積為(left\_max - height\[left\]) - 3.1.2 否則無法積水,即積水面積為 0 - 3.2 左指針右移一位 - 3.3 如果 height\[left\] >= height\[right\] - 3.3.1 如果 height\[right\] >= right\_max, 則當前格子積水面積為(right\_max - height\[right\]) - 3.3.2 否則無法積水,即積水面積為 0 - 3.4 右指針左移一位 ### 代碼 代碼支持 Python3,C++: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trap</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n = len(heights) l_max = r_max = <span class="hljs-params">0</span> l, r = <span class="hljs-params">0</span>, n - <span class="hljs-params">1</span> ans = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> l < r: <span class="hljs-keyword">if</span> heights[l] < heights[r]: <span class="hljs-keyword">if</span> heights[l] < l_max: ans += l_max - heights[l] <span class="hljs-keyword">else</span>: l_max = heights[l] l += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">if</span> heights[r] < r_max: ans += r_max - heights[r] <span class="hljs-keyword">else</span>: r_max = heights[r] r -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> ans ``` ``` ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">trap</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& heights)</span> </span>{ <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>, right = heights.size() - <span class="hljs-params">1</span>; <span class="hljs-keyword">int</span> ans = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> left_max = <span class="hljs-params">0</span>, right_max = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (left < right) { <span class="hljs-keyword">if</span> (heights[left] < heights[right]) { heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]); ++left; } <span class="hljs-keyword">else</span> { heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]); --right; } } <span class="hljs-keyword">return</span> ans; } }; ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) ## 相關題目 - [84.largest-rectangle-in-histogram](https://github.com/azl397985856/leetcode/blob/master/problems/84.largest-rectangle-in-histogram.md) 更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看