32. Longest Valid Parentheses

這題用了一個stack的技巧, 說真的這個技巧我還是不太會用

我們去維護一個stack, 然後他的最上層代表上一個substr的終點的index

所以第一個值我們會push -1進去

我們遇見左括號, 就會直接推入

遇見右括號, 就會拿出最上面那個, 然後結算長度, 這邊注意到結算長度時

我們是取上上個, 也就是拿掉最上面那個後還留在stack裡面的最上面那個

那問題來拉, 如果第一個就是右括號怎辦, 所以我們取出-1後, 就會隨機把這個右括號的index在推進去, 等於是說接下來的括號都會從這個新的底開始結算

可以試著推導看看, 我舉一個例子幫忙紀錄

stack [-1]
string = "())(())"
maxlen = 0
i = 0
stack[-1, 0]
i = 1
stack[-1], maxlen = max(maxlen, 1 -(-1)), maxlen = 2
i = 2
stack[2], 取出-1後再推入2
i = 3 
stack[2,3]
i = 4
stack[2,3,4]
i = 5 
stack[2,3] maxlen = max(maxlen, 5 - 3) maxlen = 2
i = 6
stack[2] maxlen = max(maxlen, 6 - 2) maxlen = 4

算是stack中的經典吧

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int res = 0;
        for(int i = 0; i < s.size();i++){
            if(s[i] == '('){
                st.push(i);
            }else{
                st.pop();
                if(st.empty()){
                    st.push(i);
                }else{
                    res = max(i - st.top(), res);
                }
            }
        }
        return res;
    }
};