Longest Valid Parentheses - 每日算法

每日算法——leetcode系列

问题 Longest Valid Parentheses

Difficulty: Hard

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

class Solution {public:    int longestValidParentheses(string s) {}};

翻译

最长有效括号

难度系数：中等
给定一个仅仅包含'('或 ')'的字符串，找出其中最长有效括号组成的子集的长度。
字符串"(()"，它的最长有效号符子集是"()"，长度为2。
另一个例子")()())"，它的最长有效括号子集是"()()"，长度是4。

思路

假定：起始匹配位置startIndex=-1;最大匹配长度maxLen=0，当前遍历的索引为i:
遍历字符串：
遍历到的字符有两种情况：

• 当前字符为左括号,压栈, startIdnex = i;

• 当前字符为右括号

1. 如果栈为空,表示没有匹配的左括号,无任何操作

2. 如果栈不空,出栈;

经过上面的第二步操作后，栈有两种情况：

• 栈空, 则i-startIndex为当前找到的匹配长度,检查i-startIndex是否比maxLen
  更大,如果更大就更新maxLen;

• 栈不空,则当前栈顶元素t是上次匹配的最后位置。,检查i-t
  是否比ml更大,使得ml得以更新。

注:因为入栈的一定是左括号,显然没有必要将它们本身入
栈,应该入栈的是该字符在字符串中的索引。

代码

class Solution {public:    void nextPermutation(vector<int>& nums) {        size_t len = nums.size();        if (len == 1 || len == 0){return;        }        int firstBreakNum = -1;        size_t firstBreakIndex = -1;        for (size_t i = len ;i > 1; --i){if (nums[i-1] > nums[i-2]){    firstBreakNum = nums[i-2];    firstBreakIndex = i - 2;    break;}        }        // 没找到打破升序规律的，那就全部升序排列        if (firstBreakNum == -1){reverse(nums.begin(), nums.end());return;        }        for (size_t i = len; i > 1; --i){if (nums[i-1] > firstBreakNum){    swap(nums[i-1], nums[firstBreakIndex]);    break;}        }        auto iter = nums.begin();        for (size_t i = 0; i < firstBreakIndex + 1; ++i){iter++;        }        reverse(iter, nums.end());    }};

还可以继续优化