32. Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses?envType=problem-list-v2&envId=rabvlt31

這題我想在資工系茁壯成長的人一定不陌生，完全就是各種程式課程的回憶。

關於括弧的題目我也做過不少，一開始看到這題標 hard 想說哈哈我一定秒殺，括弧我已經熟到不能再熟了。結果實際下去跑，各種邊界條件我愣是搞不定。演算法換了八百種，程式碼越寫越長，這題大該花了四小時有吧😃

最終我寫了一個土法煉鋼篇暴力的程式碼，雖然只 beat 5%，但總算還是寫出來了。

class Solution {
public:
    int longestValidParentheses(string s) {
        std::stack<char> par;
        std::stack<int> score;
        vector<int> par_len;
        int ans = 0;
        int temp = 0;

        for (char p: s) {
            temp = 0;
            if(p == '(') {
                par.push('(');
                score.push(0);
            }
            else if(!par.empty()) {
                par.pop();
                if(score.top() == 0) {
                    score.pop();
                    while (!score.empty() && score.top() != 0) {
                        temp += score.top();
                        score.pop();
                    }
                    temp += 2;
                    score.push(temp);
                    ans = max(ans, temp);
                }
                else {

                    while (!score.empty() && score.top() != 0) {
                        temp += score.top();
                        score.pop();
                    }
                    score.pop();
                    while (!score.empty() && score.top() != 0) {
                        temp += score.top();
                        score.pop();
                    }
                    temp += 2;
                    score.push(temp);
                    ans = max(ans, temp);
                }
                
            }
            else {
                while (!score.empty()) {
                    score.pop();
                }
            }

        }

        return ans;
    }
};

有空再來談談我當時的腦迴路。

Best Solution

在點開討論區前，我已經做好被爆擊的準備了。畢竟這是一題經典的 stack 題目，我總是感覺他能夠被簡單的以 stack 化解，但我就是寫不出 AC 版本，歐嗚痛苦～

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int max_len = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    max_len = max(max_len, i - st.top());
                }
            }
        }

        return max_len;        
    }
};

這都是些啥！！！只有 23 行！！！

驚呆了這個解法其實想法很簡單，不會很難知道他在寫什麼，卻很難自己想出來，leetcode 討論區是什麼聰明人的聚集地嗎？

抽象 high level 的去說，這個 i 指的是右括弧位置，st.top() 不是左括弧！因為左括弧被 pop 掉了 (line 12)。st.stop是指這整個合法的連續括弧的前一個不合法位置，所以用 i - st.top() 就是整個合法的長度！

太厲害了請收下我膝蓋。