<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>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0221. 最大正方形 ## 題目地址(221. 最大正方形) <https://leetcode-cn.com/problems/maximal-square/> ## 題目描述 ``` <pre class="calibre18">``` 在一個由 0 和 1 組成的二維矩陣內,找到只包含 1 的最大正方形,并返回其面積。 示例: 輸入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 輸出: 4 ``` ``` ## 前置知識 - 動態規劃 - 遞歸 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 ![](https://img.kancloud.cn/1f/cd/1fcd397f463f55fad67e330b2a07e24a_420x355.jpg) 符合直覺的做法是暴力求解處所有的正方形,逐一計算面積,然后記錄最大的。這種時間復雜度很高。 我們考慮使用動態規劃,我們使用dp\[i\]\[j\]表示以matrix\[i\]\[j\]為右下角的頂點的可以組成的最大正方形的邊長。 那么我們只需要計算所有的i,j組合,然后求出最大值即可。 我們來看下dp\[i\]\[j\] 怎么推導。 首先我們要看matrix\[i\]\[j\], 如果matrix\[i\]\[j\]等于0,那么就不用看了,直接等于0。 如果matrix\[i\]\[j\]等于1,那么我們將matrix\[\[i\]\[j\]分別往上和往左進行延伸,直到碰到一個0為止。 如圖 dp\[3\]\[3\] 的計算。 matrix\[3\]\[3\]等于1,我們分別往上和往左進行延伸,直到碰到一個0為止,上面長度為1,左邊為3。 dp\[2\]\[2\]等于1(之前已經計算好了),那么其實這里的瓶頸在于三者的最小值, 即`Min(1, 1, 3)`, 也就是`1`。 那么dp\[3\]\[3\] 就等于 `Min(1, 1, 3) + 1`。 ![](https://img.kancloud.cn/84/59/8459a651d6f2b68dde7e87cfaaf02519_383x321.jpg) dp\[i - 1\]\[j - 1\]我們直接拿到,關鍵是`往上和往左進行延伸`, 最直觀的做法是我們內層加一個循環去做就好了。 但是我們仔細觀察一下,其實我們根本不需要這樣算。 我們可以直接用dp\[i - 1\]\[j\]和dp\[i\]\[j -1\]。 具體就是`Min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1`。 ![](https://img.kancloud.cn/fe/84/fe84a3d7426b688b280cc40dec967bbf_365x280.jpg) 事實上,這道題還有空間復雜度O(N)的解法,其中N指的是列數。 大家可以去這個[leetcode討論](https://leetcode.com/problems/maximal-square/discuss/61803/C%2B%2B-space-optimized-DP)看一下。 ## 關鍵點解析 - DP - 遞歸公式可以利用dp\[i - 1\]\[j\]和dp\[i\]\[j -1\]的計算結果,而不用重新計算 - 空間復雜度可以降低到O(n), n為列數 ## 代碼 代碼支持:Python,JavaScript: 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">maximalSquare</span><span class="hljs-params">(self, matrix: List[List[str]])</span> -> int:</span> res = <span class="hljs-params">0</span> m = len(matrix) <span class="hljs-keyword">if</span> m == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> n = len(matrix[<span class="hljs-params">0</span>]) dp = [[<span class="hljs-params">0</span>] * (n + <span class="hljs-params">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m + <span class="hljs-params">1</span>)] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, m + <span class="hljs-params">1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): dp[i][j] = min(dp[i - <span class="hljs-params">1</span>][j], dp[i][j - <span class="hljs-params">1</span>], dp[i - <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>]) + <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> matrix[i - <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>] == <span class="hljs-string">"1"</span> <span class="hljs-keyword">else</span> <span class="hljs-params">0</span> res = max(res, dp[i][j]) <span class="hljs-keyword">return</span> res ** <span class="hljs-params">2</span> ``` ``` JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=221 lang=javascript * * [221] Maximal Square */</span> <span class="hljs-title">/** * @param {character[][]} matrix * @return {number} */</span> <span class="hljs-keyword">var</span> maximalSquare = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">matrix</span>) </span>{ <span class="hljs-keyword">if</span> (matrix.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> dp = []; <span class="hljs-keyword">const</span> rows = matrix.length; <span class="hljs-keyword">const</span> cols = matrix[<span class="hljs-params">0</span>].length; <span class="hljs-keyword">let</span> max = <span class="hljs-params">Number</span>.MIN_VALUE; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < rows + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">if</span> (i === <span class="hljs-params">0</span>) { dp[i] = <span class="hljs-params">Array</span>(cols + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>); } <span class="hljs-keyword">else</span> { dp[i] = [<span class="hljs-params">0</span>]; } } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < rows + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j < cols + <span class="hljs-params">1</span>; j++) { <span class="hljs-keyword">if</span> (matrix[i - <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>] === <span class="hljs-string">"1"</span>) { dp[i][j] = <span class="hljs-params">Math</span>.min(dp[i - <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>], dp[i - <span class="hljs-params">1</span>][j], dp[i][j - <span class="hljs-params">1</span>]) + <span class="hljs-params">1</span>; max = <span class="hljs-params">Math</span>.max(max, dp[i][j]); } <span class="hljs-keyword">else</span> { dp[i][j] = <span class="hljs-params">0</span>; } } } <span class="hljs-keyword">return</span> max * max; }; ``` ``` ***復雜度分析*** - 時間復雜度:O(M?N)O(M \* N)O(M?N),其中M為行數,N為列數。 - 空間復雜度:O(M?N)O(M \* N)O(M?N),其中M為行數,N為列數。
                  <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>

                              哎呀哎呀视频在线观看