thumbnail: https://s2.ax1x.com/2019/04/05/ARfLq0.jpg
title: 32. Longest Valid Parentheses
toc: true
tags: leetcode
categories: leetcode
comments: true
题目描述：最长有效括号
给定一个只包含(和)的字符串，找出最长的包含有效的子串的长度。
示例1：
Input:
"(()"
Output:
2
示例2：
Input:
"")()())""
Output:
4
分析：
- 有效的括号是指任何可以连续可以成对的括号组成的字符串，例如
()()(),((())),()(()())等等均为有效的括号 - 遇到类似
成对消除的题目，首先就应该考虑到用栈这种数据结构来解决问题
思路：既然使用栈来解决这样的问题，那如何记录有效括号的长度呢？为了说得更明白一点，下面以输入字符串为()((()())(为例子。
| # | ( | ) | ( | ( | ( | ) | ( | ) | ) | ( |
|---|---|---|---|---|---|---|---|---|---|---|
| -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
- 首先，可以明确一点的是，用栈可以去消除有效的括号
消除方法：遍历给定字符串，当满足栈顶元素为(并当前字符为)时，弹出栈顶元素；其他情况时，当前字符入栈；完成此操作后，栈中元素只剩下字符串中-1,2,9对应的字符，如下表：
| # | ( | ( | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
- 上一步仅仅是消除有效的括号，但是如何和本题求最长有效括号联系在一起呢？
其实可以这样想，当我们消除掉有效括号后，栈中剩下的元素包含了有效括号的前面和后面的元素，有效括号前面一个和后面一个元素之间的距离不就是有效括号的长度吗？在这里，就对应于上表 的1-(-1)和8-2,这些长度里面最大的就是要求最长有效括号的长度，即8-2=6 - 因此，在栈中不仅要存遍历的当前字符，还要存放当前字符对应的索引位置，可以考虑在栈中放一个数组，数组第一个元素为
(或),第二个元素为当前字符对应的索引。 -
总结：
- 初始化栈，栈中数组第一个元素随便放，第二个放入-1
- 遍历给定字符串
- 判断栈顶元素为
(并当前字符为)时，弹出栈顶元素，这时候栈顶元素就变成了有效字符串前一个字符了，此时遍历的索引值减去当前栈顶元素对应的索引，每次这样得到的差值求个最大值，此时对应的最大差值即最长有效括号的长度。 - 算法的时间复杂度为
n
以下演示遍历过程：
i=0
| s.charAt(i) | # | ( | ) | ( | ( | ( | ) | ( | ) | ) | ( |
|---|---|---|---|---|---|---|---|---|---|---|---|
| i | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
此时，栈中元素状态：
| arr[0] | # |
|---|---|
| arr[1] | -1 |
不满足栈顶元素为(,当前遍历元素为),当前遍历元素和对应索引入栈：
栈中元素状态为：
| arr[0] | # | ( |
|---|---|---|
| arr[1] | -1 | 0 |
i=1 时,满足括号消除条件：
栈中元素状态为：
| arr[0] | # |
|---|---|
| arr[1] | -1 |
max = i-(-1)=2
...
...
若是理解不够清楚，读者可以自己尝试。
以此类推，每次栈弹出时，栈顶元素对应的都是有效括号的前一个元素，同时更新max,最终遍历完字符串得到的max即为要返回的结果。代码如下：
class Solution {
public int longestValidParentheses(String s) {
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{0,-1});
int max = 0,cnt = 0;
for(int i=0;i<s.length();i++){
int temp = s.charAt(i);
if(!stack.isEmpty() && stack.peek()[0]==40 && temp==41){
stack.pop();
cnt = i-stack.peek()[1];
if(cnt>max) max=cnt;
}else{
stack.push(new int[]{temp,i});
}
}
return max;
}
}
该解法运行结果对应的时间和空间复杂度如下图：
eet
要注意的问题：栈中放入的是整型数组，因此遍历得到的字符要转换为整型(对应于temp的自动类型转换)，(的整型值对应于40，)的整型值对应于41，当然，若是不知道他们对应的整型值，也可以用字符去判断，但在push到栈中时，要对temp进行强制类型转换。
