[LeetCode] Longest Valid Parentheses

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

解題思路：

題意找到最長有效括號的子串長度。求最大問題，第1想法就是動態計劃，但是，通項公式真不好找。喜刷刷http://bangbingsyb.blogspot.jp/2014/11/leetcode-longest-valid-parentheses.html中有相干說明，我沒有理解，。

由因而括號問題，可以用棧來實現。這跟判斷棧是不是有效不同。注意到，若某個右括號不與前面的某個左括號匹配，那末，這個右括號可以作為子串分割標記。大體思想是，若遇到左括號，無條件將左括號的下標入棧。若遇到右括號，若棧頂是左括號與之匹配，將左括號出棧，更新最大的長度值。若棧頂沒有左括號與之匹配，將該右括號的下標入棧，作為分割字符。代碼以下：

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈