1. 32. 最长有效括号
    2.     给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
    3.     示例 1：输入：s = "(()"，输出：2，解释：最长有效括号子串是 "()"
    4.     示例 2：输入：s = ")()())"，输出：4，解释：最长有效括号子串是 "()()"
    5.     示例 3：输入：s = ""，输出：0
    6.     来源：力扣（LeetCode）
    7.     链接：https://leetcode-cn.com/problems/longest-valid-parentheses
    8.     著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    这道题目实际上已经不是第一次见到了，从最早的学习数据结构的时候，在堆栈一章就是以括号匹配和算式匹配作为例子进行介绍。

    一做到这道题实际上就能联想到另一道LeetCode的简单题：

    1. 20. 有效的括号
    2.     给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    3.     有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
    4.      示例 1：输入：s = "()"，输出：true
    5.     示例 2：输入：s = "()[]{}"，输出：true
    6.     示例 3：输入：s = "(]"，输出：false
    7.     示例 4：输入：s = "([)]"，输出：false
    8.     示例 5：输入：s = "{[]}"，输出：true
    9.     来源：力扣（LeetCode）
    10.     链接：https://leetcode-cn.com/problems/valid-parentheses
    11.     著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    这道难度较低的题目更相似于我们在数据结构刚接触堆栈的时候能接触的简单的数据结构的题目。这道题的解法比较简单，这里略去不表。

    为什么要用堆栈，因为这道题在后续的遍历过程中要于之前遍历的结果进行对比。这是很重要的一个原因导致堆栈的使用。当遍历时需要对前后结果进行对比时，实际上使用双指针也是一种方法，但是双指针的存在容易增加时间复杂度，而且，此处从后向前遍历只与最近的之前遍历结果相比较（因为括号需匹配最近的一个）。所以综上所述，使用一个堆栈是最佳的用于解决括号匹配的数据结构。

    接下来回到一开始的 LeetCode 32. 最长有效括号，这道看似简单的题目却让我纠结了很久。这道题主要并不是在判断是否存在合法的括号序列，真正重要的是找到其中的合法括号序列并求出最长的序列。基于这样的要求，实际上就会出现几个比较难避开的坑：

    1. “)()())”，较为简单的连续多个独立的有效括号
    2. “)(“，全不匹配的无效括号
    3. “(()))”，多重包裹的有效括号
    4. “()(()))”，独立括号连接多重包裹有效括号

    以上四种情况，第四种相对而言是最容易出现的错误情况。在这种情况下，任何少考虑一个方面都会出现错误。此处就以”(())())”为例，说明时候能对最长长度进行修改，是一个很重要的结束条件。在第一次写这道题的时候，我出现了一个很简单的错误，那就是在”()”的时候就停止了向下继续并将此时的长度用于去比较最长长度。过程大概是先入栈一个”(“， 在之后向后寻找”)”，找到之后对比栈顶的符号若匹配则弹出。所以本题的关键实际上就是如何判断此时已经到达了需要把临时长度与目前最长长度进行对比的情况。

    第一次我使用了当辅助栈为空作为条件，当栈为空就把此时的临时长度拿去与最大长度进行对比。这种情况是明显错误的，如果是”()()”的情况会直接导致临时长度在为2的情况就结束判断，所以需要将结束条件进行修改。

    第二次我使用了有效括号之后出现不合法括号作为条件，当在有效括号之后（即堆栈空了）出现非法括号时，就结束了向下检索并将临时长度去与最长长度进行对比。但这个条件只能通过不到50%的测试样例，因为很明显把它用来检索第四个样例会出现不小的问题。因为在有效括号之后出现了”((“的情况就会被我认为是不合法的括号，所以直接暂停向下检索并将临时长度与目前最长长度进行一个对比。

    所以，最后综合上述的情况，可以对算法进行一个最终的修改 —— 始终保持栈底元素为当前已经遍历过的元素中最后一个没有被匹配的右括号的下标。也就是不向栈内送入符号而是向栈内输入下标，维护下标以获得最长长度。

    1. class Solution {
    2. public:
    3.     int longestValidParentheses(string s) {
    4.         if (s.size() < 2) // 当长度小于2时实际上是肯定不会出现可以匹配的情况的
    5.             return 0;
    6.         int maxRes = 0; // 用来作为目前最长长度
    7.         stack<int> st; // 用于辅助堆栈
    8.         st.push(-1); // 因为一开始并没有起始的下标，所以将-1下标先送入堆栈做保留
    9.         for (int i = 0; i < s.size(); i ++)
    10.         {
    11.             if (s[i] == '(') // 当出现'('时，可以将当前下标送入堆栈
    12.                 st.push(i); 
    13.             else // 当出现')'时，首先退出一个'('的下标
    14.             {
    15.                 st.pop();
    16.                 if (st.empty()) // 若为空则保留此时的下标
    17.                     st.push(i);
    18.                 else
    19.                     maxRes = max(maxRes, i - st.top()); // 若不为空则对比此时最长长度
    20.             }
    21.         }
    22.         return maxRes;
    23.     }
    24. };

    当然，本道题在这里使用堆栈的方法就能正常解决了，时间复杂度为O(n)，空间复杂度为O(n)。本题在解决时其实还可以使用动态规划的方法，但是实际上在面试笔试的过程中，要能找到最佳的解决方法是很重要的，但是如果能够养成一个一看到括号就能想到使用堆栈并解决这个问题，那也是一个很好的办法。虽然可能不是最优解，但可以保证下限，能顺利解决该问题。