题解 | #最长的括号子串#

#include <algorithm>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    bool canpop(char a, char b) {
        return (a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' &&
                b == ')');
    }
    int longestValidParentheses(string s) {

        vector<bool> legalsubstrs(s.length(), false);
        cout << endl;
        stack<char> stk;
        stack<int> stkindex;
        for (int j = 0; j < s.length(); j++) {
            if (s[j] == '{' || s[j] == '[' || s[j] == '(') {
                stk.push(s[j]);
                stkindex.push(j);
            } else {
                if (stk.empty() || !canpop(stk.top(), s[j])) {
                    stk.push(s[j]);
                    stkindex.push(j);
                } else {
                    stk.pop();
                    int legalindex = stkindex.top();
                    stkindex.pop();
                    legalsubstrs[j] = true;
                    legalsubstrs[legalindex] = true;
                }
            }
        }
        int maxLength = 0;
        int curLength = 0;
        for (auto u : legalsubstrs) {
            if (u) {
                curLength++;
            } else {
                curLength = 0;
            }
            if (curLength > maxLength) {
                maxLength = curLength;
            }
        }
        return maxLength;
    }
};

先用栈，标记所有成对括号，然后再找标记数组（这里用vector<bool>，其实也就是bitset）里面最长连续为1的序列