add q32

yuanguangxin · yuanguangxin · commit f306cb33328a · 2020-03-26T20:38:12.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/README.md b/README.md
@@ -58,6 +58,7 @@
 ### 栈相关
 
 * [q20_有效的括号](/src/栈相关/q20_有效的括号)
+* [q32_最长有效括号](/src/栈相关/q32_最长有效括号)
 * [q224_基本计算器](/src/栈相关/q224_基本计算器)
 * [q316_去除重复字母](/src/栈相关/q316_去除重复字母)
 
diff --git a/src/栈相关/q32_最长有效括号/Solution.java b/src/栈相关/q32_最长有效括号/Solution.java
@@ -0,0 +1,38 @@
+package 栈相关.q32_最长有效括号;
+
+import java.util.Stack;
+
+/**
+ * 利用索引栈 o(n)
+ */
+public class Solution {
+
+    public int longestValidParentheses(String s) {
+        if (s == null || s.length() < 2) {
+            return 0;
+        }
+
+        int maxLen = 0;
+        Stack<Integer> stack = new Stack<>();
+        stack.push(-1);
+        for (int i = 0; i < s.length(); i++) {
+            char temp = s.charAt(i);
+            if (temp == '(') {
+                stack.push(i);
+            } else {
+                stack.pop();
+                if (stack.empty()) {
+                    stack.push(i);
+                } else {
+                    maxLen = Math.max(maxLen, i - stack.peek());
+                }
+            }
+        }
+
+        return maxLen;
+    }
+
+    public static void main(String[] args) {
+        System.out.println(new Solution().longestValidParentheses(")()())"));
+    }
+}
