題目描述
給你一個(gè)只包含 '(' 和 ')' 的字符串拍顷，找出最長(zhǎng)有效（格式正確且連續(xù)）括號(hào)子串的長(zhǎng)度。
示例 1：
輸入：s = "(()"
輸出：2
解釋：最長(zhǎng)有效括號(hào)子串是 "()"
示例 2：
輸入：s = ")()())"
輸出：4
解釋：最長(zhǎng)有效括號(hào)子串是 "()()"
示例 3：
輸入：s = ""
輸出：0
提示：
0 <= s.length <= 3 * 104
s[i] 為 '(' 或 ')'
題解
始終保持棧底元素為當(dāng)前已經(jīng)遍歷過(guò)的元素中最后一個(gè)沒(méi)有被匹配的右括號(hào)的下標(biāo)
class Solution {
public int longestValidParentheses(String s) {
int max = 0;
Stack<Integer> st = new Stack<>();
st.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
st.push(i);
} else {
st.pop();
if (st.isEmpty()) {
st.push(i);
} else {
max = Math.max(max, i - st.peek());
}
}
}
return max;
}
}
