leetcode-32. Longest Valid Parentheses

本文主要是介绍leetcode-32. Longest Valid Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode-32. 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.

这题应该怎么想，首先括号有一些自身的特性，比如说只有有左括号则必须有右括号，如果括号不成双则说明无效。所以所有这种判断括号有效性的题目都可以用栈来解决，遇到左括号就压入栈，遇到右括号就弹出一个栈（当然还要判断栈的元素数量）。

这里的思路就是用一个指针从左往右指，然后看当前位置是否是左括号，

如果是左括号就将当前位置压人栈，
如果是右括号就判断当前栈是否为空，
- 如果是空则说明之前数据违法了，那就从当前位置开始判断之后的括号是否有效。
- 如果不是则抛出一个左括号与当前指针的右括号相消，这时在判断栈是否为空。
  - 如果这时栈为空了，则说明以当前的left为节点的区域已经判断完毕。更新一下max；
  - 如果这时栈不为空，则说明以当前的i为右节点，栈顶元素为做节点的区域是当前的最大正确区域。

非常漂亮的解法，也没想出来，我想出来的没这么快。贴一下来源

答案来源

public class Solution {public int longestValidParentheses(String s) {if(s==null || s.length()<1) return 0;int max = 0;int left = -1;Stack<Integer> sta = new Stack<Integer>();for(int i = 0 ; i < s.length(); i++){if(s.charAt(i)=='('){sta.push(i);}else{if(sta.isEmpty()) left = i;else{sta.pop();if(sta.isEmpty()) max=Math.max(max,i-left);else max=Math.max(max,i-sta.peek());}}}return max;}
}