image.png

方法一：栈

首先我们先要看懂题目的意思（没错，开始我就没搞懂）

感觉用到我们实际的代码中比较好里面，最长有效括号的重点在于有效，就比如 (( a + b ) + ( c + d ) + e ) 最长的有效括号就是 第一个左括号，和最后一个右括号。

那么我们可以观察出

  • 括号都是成对出现才会是有效的
  • 右括号一定在左括号后出现才是有效的

找到有效的括号能够找到，那么“最长”有效括号也就不难了，使用一个变量存放就可以了。

所以我们可以使用一个辅助栈存放待匹配的左括号，

  • 遍历到左括号，存入栈中
  • 遍历到右括号，出栈一个元素
    • 栈为空：将该元素 push 进栈（作为参照元素，后续计算 长度 的时候会用到）
    • 栈不为空：记录下两个括号的 index 差值。

同时因为辅助栈里面存放的都是左括号，所以只需要将 index 存入即可。

  1. class Solution {
  2. public:
  3.     int longestValidParentheses(string s) {
  4.         int maxans = 0;
  5.         stack<int> stk;
  6.         stk.push(-1);
  7.         for (int i = 0; i < s.length(); i++) {
  8.             if (s[i] == '(') {
  9.                 stk.push(i);
  10.             } else {
  11.                 stk.pop();
  12.                 if (stk.empty()) {
  13.                     stk.push(i);
  14.                 } else {
  15.                     maxans = max(maxans, i - stk.top());
  16.                 }
  17.             }
  18.         }
  19.         return maxans;
  20.     }
  21. };
  23. 作者：LeetCode-Solution
  24. 链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
  25. 来源：力扣（LeetCode）
  26. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：动态规划