<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之旅 廣告
                # 0032. 最長有效括號 ## 題目地址(32. 最長有效括號) <https://leetcode-cn.com/problems/longest-valid-parentheses/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個只包含 '(' 和 ')' 的字符串,找出最長的包含有效括號的子串的長度。 示例 1: 輸入: "(()" 輸出: 2 解釋: 最長有效括號子串為 "()" 示例 2: 輸入: ")()())" 輸出: 4 解釋: 最長有效括號子串為 "()()" ``` ``` ## 前置知識 - 動態規劃 ## 暴力(超時) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ### 思路 符合直覺的做法是:分別計算以 i 開頭的 最長有效括號(i 從 0 到 n - 1·),從中取出最大的即可。 ### 代碼 代碼支持: Python ``` <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">longestValidParentheses</span><span class="hljs-params">(self, s: str)</span> -> int:</span> n = len(s) ans = <span class="hljs-params">0</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">validCnt</span><span class="hljs-params">(start)</span>:</span> <span class="hljs-title"># cnt 為 ) 的數量減去 ( 的數量</span> cnt = <span class="hljs-params">0</span> ans = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(start, n): <span class="hljs-keyword">if</span> s[i] == <span class="hljs-string">'('</span>: cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> s[i] == <span class="hljs-string">')'</span>: cnt -= <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> cnt < <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> i - start <span class="hljs-keyword">if</span> cnt == <span class="hljs-params">0</span>: ans = max(ans, i - start + <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> ans <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): ans = max(ans, validCnt(i)) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(N2)O(N^2)O(N2) - 空間復雜度:O(1)O(1)O(1) ## 棧 ### 思路 主要思路和常規的括號解法一樣,遇到'('入棧,遇到')'出棧,并計算兩個括號之間的長度。 因為這個題存在非法括號對的情況且求是合法括號對的最大長度 所以有兩個注意點是: 1. **棧中存的是符號的下標** 2. **當棧為空時且當前掃描到的符號是')'時,需要將這個符號入棧作為分割符** 3. 棧中初始化一個 -1,作為**分割符** ### 代碼 - 語言支持: Python, javascript javascript code: ``` <pre class="calibre18">``` <span class="hljs-title">// 用棧來解</span> <span class="hljs-keyword">var</span> longestValidParentheses = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s</span>) </span>{ <span class="hljs-keyword">let</span> stack = <span class="hljs-keyword">new</span> <span class="hljs-params">Array</span>(); <span class="hljs-keyword">let</span> longest = <span class="hljs-params">0</span>; stack.push(<span class="hljs-params">-1</span>); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < s.length; i++) { <span class="hljs-keyword">if</span> (s[i] === <span class="hljs-string">"("</span>) { stack.push(i); } <span class="hljs-keyword">else</span> { stack.pop(); <span class="hljs-keyword">if</span> (stack.length === <span class="hljs-params">0</span>) { stack.push(i); } <span class="hljs-keyword">else</span> { longest = <span class="hljs-params">Math</span>.max(longest, i - stack[stack.length - <span class="hljs-params">1</span>]); } } } <span class="hljs-keyword">return</span> longest; }; ``` ``` 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">longestValidParentheses</span><span class="hljs-params">(self, s: str)</span> -> int:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> res = <span class="hljs-params">0</span> stack = [<span class="hljs-params">-1</span>] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(s)): <span class="hljs-keyword">if</span> s[i] == <span class="hljs-string">"("</span>: stack.append(i) <span class="hljs-keyword">else</span>: stack.pop() <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> stack: stack.append(i) <span class="hljs-keyword">else</span>: res = max(res, i - stack[<span class="hljs-params">-1</span>]) <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## O(1) 空間 ### 思路 我們可以采用解法一中的計數方法。 - 從左到右遍歷一次,并分別記錄左右括號的數量 left 和 right。 - 如果 right > left ,說明截止上次可以匹配的點到當前點這一段無法匹配,重置 left 和 right 為 0 - 如果 right == left, 此時可以匹配,此時有效括號長度為 left + right,我們獲得一個局部最優解。如果其比全局最優解大,我們更新全局最優解 值得注意的是,對形如 `(((()` 這樣的,更新全局最優解的邏輯永遠無法執行。一種方式是再從右往左遍歷一次即可,具體看代碼。 > 類似的思想有哨兵元素,虛擬節點。只不過本題無法采用這種方法。 ### 代碼 代碼支持:Java,Python ``` <pre class="calibre18">``` <span class="hljs-keyword">public</span> <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">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">longestValidParentheses</span><span class="hljs-params">(String s)</span> </span>{ <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>, right = <span class="hljs-params">0</span>, maxlength = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < s.length(); i++) { <span class="hljs-keyword">if</span> (s.charAt(i) == <span class="hljs-string">'('</span>) { left++; } <span class="hljs-keyword">else</span> { right++; } <span class="hljs-keyword">if</span> (left == right) { maxlength = Math.max(maxlength, left + right); } <span class="hljs-keyword">if</span> (right > left) { left = right = <span class="hljs-params">0</span>; } } left = right = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = s.length() - <span class="hljs-params">1</span>; i >= <span class="hljs-params">0</span>; i--) { <span class="hljs-keyword">if</span> (s.charAt(i) == <span class="hljs-string">'('</span>) { left++; } <span class="hljs-keyword">else</span> { right++; } <span class="hljs-keyword">if</span> (left == right) { maxlength = Math.max(maxlength, left + right); } <span class="hljs-keyword">if</span> (left > right) { left = right = <span class="hljs-params">0</span>; } } <span class="hljs-keyword">return</span> maxlength; } } ``` ``` ``` <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">longestValidParentheses</span><span class="hljs-params">(self, s: str)</span> -> int:</span> ans = l = r = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s: <span class="hljs-keyword">if</span> c == <span class="hljs-string">'('</span>: l += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: r += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> l == r: ans = max(ans, l + r) <span class="hljs-keyword">if</span> r > l: l = r = <span class="hljs-params">0</span> l = r = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> s[::<span class="hljs-params">-1</span>]: <span class="hljs-keyword">if</span> c == <span class="hljs-string">'('</span>: l += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: r += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> l == r: ans = max(ans, l + r) <span class="hljs-keyword">if</span> r < l: l = r = <span class="hljs-params">0</span> <span class="hljs-keyword">return</span> ans ``` ``` ## 動態規劃 ### 思路 所有的動態規劃問題, 首先需要解決的就是如何尋找合適的子問題. 該題需要我們找到最長的有效括號對, 我們首先想到的就是定義**dp\[i\]為前 i 個字符串的最長有效括號對長度**, 但是隨后我們會發現, 這樣的定義, 我們無法找到 dp\[i\]和 dp\[i-1\]的任何關系. 所以, 我們需要重新找一個新的定義: 定義**dp\[i\]為以第 i 個字符結尾的最長有效括號對長度**. 然后, 我們通過下面這個例子找一下 dp\[i\]和 dp\[i-1\]之間的關系. ``` <pre class="calibre18">``` s = <span class="hljs-string">'(())())'</span> ``` ``` 從上面的例子我們可以觀察出一下幾點結論(**描述中 i 為圖中的 dp 數組的下標, 對應 s 的下標應為 i-1, 第 i 個字符的 i 從 1 開始**). 1. base case: 空字符串的最長有效括號對長度肯定為 0, 即: dp\[0\] = 0; 2. s 的第**1**個字符結尾的最長有效括號對長度為 0, s 的第**2**個字符結尾的最長有效括號對長度也為 0, 這個時候我們可以得出結論: 最長有效括號對不可能以'('結尾, 即: dp\[1\] = d\[2\] = 0; 3. 當 i 等于 3 時, 我們可以看出 dp\[2\]=0, dp\[3\]=2, 因為第 2 個字符(**s\[1\]**)和第 3 個字符(**s\[2\]**)是配對的; 當 i 等于 4 時, 我們可以看出 dp\[3\]=2, dp\[4\]=4, 因為我們配對的是第 1 個字符(**s\[0\]**)和第 4 個字符(**s\[3\]**); 因此, 我們可以得出結論: 如果第**i**個字符和第**i-1-dp\[i-1\]**個字符是配對的, 則 dp\[i\] = dp\[i-1\] + 2, 其中: i-1-dp\[i-1\] >= 1, 因為第 0 個字符沒有任何意義; 4. 根據第 3 條規則來計算的話, 我們發現 dp\[5\]=0, dp\[6\]=2, 但是顯然, dp\[6\]應該為 6 才對, 但是我們發現可以將"(())"和"()"進行拼接, 即: dp\[i\] += dp\[i-dp\[i\]\], 即: dp\[6\] = 2 + dp\[6-2\] = 2 + dp\[4\] = 6 根據以上規則, 我們求解 dp 數組的結果為: \[0, 0, 0, 2, 4, 0, 6, 0\], 其中最長有效括號對的長度為 6. 以下為圖解: ![](https://img.kancloud.cn/38/15/3815532606043d7960729cac46e832ff_923x443.jpg) ### 代碼 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">longestValidParentheses</span><span class="hljs-params">(self, s: str)</span> -> int:</span> mlen = <span class="hljs-params">0</span> slen = len(s) dp = [<span class="hljs-params">0</span>] * (slen + <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>, len(s) + <span class="hljs-params">1</span>): <span class="hljs-title"># 有效的括號對不可能會以'('結尾的</span> <span class="hljs-keyword">if</span> s[i - <span class="hljs-params">1</span>] == <span class="hljs-string">'('</span>: <span class="hljs-keyword">continue</span> left_paren = i - <span class="hljs-params">2</span> - dp[i - <span class="hljs-params">1</span>] <span class="hljs-keyword">if</span> left_paren >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> s[left_paren] == <span class="hljs-string">'('</span>: dp[i] = dp[i - <span class="hljs-params">1</span>] + <span class="hljs-params">2</span> <span class="hljs-title"># 拼接有效括號對</span> <span class="hljs-keyword">if</span> dp[i - dp[i]]: dp[i] += dp[i - dp[i]] <span class="hljs-title"># 更新最大有效擴對長度</span> <span class="hljs-keyword">if</span> dp[i] > mlen: mlen = dp[i] <span class="hljs-keyword">return</span> mlen ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ### 關鍵點解析 1. 第 3 點特征, 需要檢查的字符是 s\[i-1\]和 s\[i-2-dp\[i-1\]\], 根據定義可知: i-1 >= dp\[i-1\], 但是 i-2 不一定大于 dp\[i-1\], 因此, 需要檢查越界; 2. 第 4 點特征最容易遺漏, 還有就是不需要檢查越界, 因為根據定義可知: i >= dp\[i\], 所以 dp\[i-dp\[i\]\]的邊界情況是 dp\[0\]; ## 相關題目 - [20.valid-parentheses](20.valid-parentheses.html) ## 擴展 1. 如果判斷的不僅僅只有'('和')', 還有'\[', '\]', '{'和'}', 該怎么辦? 2. 如果輸出的不是長度, 而是任意一個最長有效括號對的字符串, 該怎么辦? 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_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>

                              哎呀哎呀视频在线观看