算法积累：最长有效括号

今天是一个值得庆祝的日子！

五年前，我第一次开始在力扣上练习算法题，直到今天才把 Hot 100 全部写完，这道“最长有效括号”就是我 Hot 100 的收官之题。 回想起来，我自己也有些惭愧，作为一个打定决心要做软件开发的人，竟然断断续续用了五年才把早该做好的事情做完。 而另一些本该做完的事情，可能我甚至都还没做呢。

AI 时代算法题是不是仍然有意义？ 这个问题在网上被反复讨论，大多数人认为在前 AI 时代，算法题早都没有什么意义了，只是起到一种快速筛选的作用而已。 少部分人以刷题为乐，他们也不求什么意义。我个人对算法题的态度经历了很多的转折，但到目前为止，我觉得还是有意义的。 算法题最大的意义我认为是训练我们用计算思维来思考问题和解决问题，而不是用常人视角。 这倒不是说计算思维是一种高级思维，而是作为这个时代的一个开发者，理应很熟练的用算法的视角看待世间万物，这跟人的天性可能相悖，所以就需要某种形式的训练。

题目

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。

解法

这道题可以用动态规划来解，但是我暂时觉得那种解法太不直观，给我一种无聊的炫技的感觉。 我更推荐的解法是用栈来解，这也非常符合这种括号匹配场景给人的直观印象。

我们维护一个栈，栈中的元素是序列的下标，栈顶元素表示当前有效括号序列的左边界（有效括号序列的第一个元素的索引前面的一个位置）。 初始化时需要先向其中推入一个 -1 ，表示当前有效括号序列的左边界在序列的最前面。

然后遍历括号序列，如果遇到了左括号，就将其下标推入栈中，如果遇到了右括号，则从栈顶弹出一个左括号尝试匹配。 如果弹出栈顶元素后栈空了，表示匹配失败了，此时将当前右括号的下标推入栈中，它将作为新的有效括号序列的左边界。 如果弹出栈顶元素后栈仍然非空，表示匹配成功，此时计算当前有效括号序列的长度，并更新最大长度。

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

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

        return ans;
    }
};

这种实现方案是相对来说最好理解的，而且代码简洁优雅，非常清晰。