這題看起來(lái)簡(jiǎn)單但是容易漏很多test case。

錯(cuò)誤的思路

一開始我的思路是： 遇到左括號(hào)就入棧、計(jì)數(shù)；遇到右括號(hào)先檢查棧是否為空；不為空就出棧、計(jì)數(shù)，為空就結(jié)束本次計(jì)數(shù)
上面這種思路有漏洞，比如當(dāng)(()的情況時(shí)，返回的結(jié)果將會(huì)是3

正確的方式

遇到左括號(hào)就把它的index壓棧，遇到右括號(hào)先檢查棧是否為空，為空就說(shuō)明是())這種情形，所以把start右移一位，直到找到一個(gè)(為止；
不為空就pop出一個(gè)元素，這時(shí)候要進(jìn)行第二次判空，如果為空，說(shuō)明是()了，判斷i-start+1；如果不為空就說(shuō)明是((),那么返回i-peak+1

另外說(shuō)一下，這道題Leetcode一直TLE，我以為代碼有問題，比對(duì)了半天，結(jié)果貼網(wǎng)上的代碼上去，同樣TLE..醉了，leetcode的一個(gè)很長(zhǎng)的((((((...的test case過(guò)不了（有時(shí)候能過(guò)），不知道是不是網(wǎng)絡(luò)的問題。

    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0)
            return 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int start = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    //還沒pop就empty了，說(shuō)明遇到())了
                    start = i + 1;
                } else {
                    stack.pop();
//注意 i-stack.peak()不用加1了
                    max = stack.isEmpty() ? Math.max(max, i - start + 1) : Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }

programcreek上一個(gè)更簡(jiǎn)潔的做法：
跟上面不同的是，先壓了一個(gè)-1進(jìn)stack，第二，右括號(hào)匹配之后也把當(dāng)前index壓進(jìn)去，peek就成了類似上面的start-1。

public class Solution {

    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}