目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給你一個只包含 '(' 和 ')' 的字串，找出最長有效（格式正確且連續）括號子串的長度，
示例 1：
輸入：s = "(()"
輸出：2
解釋：最長有效括號子串是 "()"
示例 2：
輸入：s = ")()())"
輸出：4
解釋：最長有效括號子串是 "()()"
示例 3：
輸入：s = ""
輸出：0
提示：
0 <= s.length <= 3 * 10^4s[i] 為 '(' 或 ')'
2、思路
(堆疊) O ( n ) O(n) O(n)
我們可以發現一個規律，每一段合法括號序列它在字串s中出現的位置一定是連續且不相交的，如下圖所示：
因此我們能想到的最直接的做法是找到每個可能的子串后判斷它是否為合法括號序列，但這樣的時間復雜度會達到 O ( n 3 ) O(n^3) O(n3) ，
有沒有一種更高效的做法？
我們知道堆疊在處理括號匹配有著天然的優勢，于是考慮用堆疊去判斷序列的合法性，遍歷整個字串s，把所有的合法括號序列按照右括號來分類，對于每一個右括號，都去求一下以這個右括號為右端點的最長的合法括號序列的左端點在什么位置，我們把每個右括號都列舉一遍之后，再取一個max，就是整個的最大長度，
具體程序如下：
-
1、用堆疊維護當前待匹配的左括號的位置，同時用
start記錄一個新的可能合法的子串的起始位置，初始設為0， -
2、如果
s[i] =='('，那么把i進堆疊， -
3、如果
s[i] == ')',那么彈出堆疊頂元素 （代表堆疊頂的左括號匹配到了右括號），出堆疊后：-
如果堆疊為空，說明以當前右括號為右端點的合法括號序列的左端點為
start，則更新答案i - start + 1， -
如果堆疊不為空，說明以當前右括號為右端點的合法括號序列的左端點為堆疊頂元素的下一個元素，則更新答案
i - st.top()，
-
-
4、遇到右括號
)且當前堆疊為空，則當前的start開始的子串不再可能為合法子串了，下一個合法子串的起始位置是i + 1，更新start = i + 1， -
5、最后回傳答案即可，
實作細節： 堆疊保存的是下標，
時間復雜度分析： 每個位置遍歷一次，最多進堆疊一次，故時間復雜度為 O ( n ) O(n) O(n)，
3、c++代碼
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
int ans = 0;
for (int i = 0,start = 0; i < s.size(); i++)
{
if (s[i] == '(') st.push(i); //左括號入堆疊
else
{
if (!st.empty())
{
st.pop(); //匹配成功
if (st.empty()) ans = max(ans, i - start + 1);
else ans = max(ans, i - st.top()); //i - st.top() + 1 - 1
}
else start = i + 1; //更新起點
}
}
return ans;
}
};
4、java代碼
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> st = new Stack<Integer>();
int ans = 0;
for(int i = 0 ,start = 0;i < s.length();i ++)
{
if( s.charAt(i) == '(') st.add(i);
else
{
if(!st.isEmpty())
{
st.pop();
if(st.isEmpty()) ans = Math.max(ans,i - start + 1);
else ans = Math.max(ans,i - st.peek());
}
else start = i + 1;
}
}
return ans;
}
}
原題鏈接： 32. 最長有效括號
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/292331.html
標籤：java
上一篇：java八大基本資料型別與運算子
下一篇：JAVA并發基石——CAS