Leetcode 32. Longest Valid Parentheses

题目

32. Longest Valid Parentheses

Difficulty: Hard
Total Accepted: 152.4K
Total Submissions: 632.8K

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

题目链接

解题报告

AC 截图

题目大意

本题要求我们寻找一个括号字符串中最长的合法符号子串长度

解题思路

验证一个字符串是否是合法的括号字符串是简单的。我们只需要将其所有的左括号入栈，然后当右括号到来时弹出一个栈内括号，如果遇到栈为空，则判定为非法。若最后结束时没有括号剩余在栈中，则说明符号串合法。

由此出发，我们可以把所有匹配的串都加上一个标识，然后再扫一遍，找出最长连续的标识即可。整个算法的时间复杂度为 O(n)。

题解

AC 截图

C++ 代码

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
 public:
  int longestValidParentheses(string& str) {
    int size = str.size();
    int max = 0, counter = 0;
    vector<bool> validArr(size, false);
    stack<int> parentheses;
    
    for (int index = 0; index < size; ++index) {
      if (str[index] == '(') parentheses.push(index);
      else if (!parentheses.empty()) {
        validArr[parentheses.top()] = true;
        validArr[index] = true;
        parentheses.pop();
      }
    }

    for (const auto &iter : validArr) {
      if (iter) {
        ++counter;
      }
      else {
        if (max < counter) {
          max = counter;
        }
        counter = 0;
      }
    }

    return ((max > counter) ? max : counter);
  }
};