【leetcode刷题笔记】032.Longest Valid
日期：20180914
题目描述：
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 "()()"
详解：
此题难度为hard，但其实并不hard。对于这样的括号匹配问题，很容易想到使用栈结构。
class Solution {
public:
int longestValidParentheses(string s) {
//初始化变量，建了一个相同长度的bool型数组，如果配对了的元素，该位置为1
stack<int> myStack;
int n = s.size();
if(n==0){
return 0;
}
bool a[n];
for(int i = 0;i<n;i++){
a[i] = 0;
}
//开始遍历
for(int i = 0;i<n;i++){
if(s[i]=='('){
myStack.push(i);
}else{
if(!myStack.empty()){//配对成功就把bool数组两个相应的位置置1.
a[myStack.top()] = true;
myStack.pop();
a[i] = true;
}
}
}
//最后还要遍历一下bool型数组，看看最大的连续的长度是多少
int tmp = 0,max = 0;
for(int i = 0;i<n;i++){
if(a[i]==0){
if(tmp>max){
max = tmp;
}
tmp = 0;
}else{
tmp++;
}
}
if(tmp>max){
max = tmp;
}
return max;
}
};
我的思路写在了注释中。这样的时间复杂度为O(N)，空间复杂度为O(N)，因为多开了一个数组。
我的用时是8ms，看了第一名的答案，用时4ms，他使用了双端队列：
class Solution {
public:
int longestValidParentheses(string s) {
deque<int> dq;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') dq.push_back(i);
else if (s[i] == ')') {
if (!dq.empty() && s[dq.back()] == '(')
dq.pop_back();
else
dq.push_back(i);
}
}
if (dq.empty()) return s.size();
int res = 0;
int j = 0;
while (!dq.empty()) {
int i = dq.front(); dq.pop_front();
res = max(res, i-j);
j = i+1;
}
if (j) res = max(res, (int) s.size()-j);
return res;
}
};
其实思路是一样的，不过在此还是复习一下双端队列吧。另外明天把STL容器和迭代器相关的知识一起复习一下。
Deque结构
如图1是deque的逻辑结构，从表面上看，deque具有连续性的存储空间，并支持随机存取功能。实际上deque并不是我们所看到的样子，其内部结构，如图2所示。
deque在实现上主要有以下两点：
-
由一段一段的定量连续空间构成，第一个区块朝某个方向扩展，最后一个区块朝相反方向扩展；
-
管理这些分段的定量连续空间，维护其整体连续的假象，并提供随机存取的接口；
Deque的能力
与vector相比，deque功能上的不同之处在于：
- 首尾两端都能快速的安插、删除元素，因此需要在两端安插、删除元素时，最好采用deque。
- 存在元素时，deque的内部结构会多一个间接过程，操作元素的效率会比vector低一些。
- 迭代器需要在不同区块间跳转，所以必须是特殊的智能指针，非一般指针。
- deque不支持对容量和内存重分配时机的控制，除了首尾两端安插、删除元素外，其他地方安插、删除元素都将导致元素的pointer、reference、iterator失效。不过，deque的内存重分配机制优于vector，因为deque不必在内存重分配时复制所有的元素。
- deque的内存区块不再被使用时，会被释放。
Deque的操作函数：
Deque的操作函数和vector操作函数基本一模一样，操作函数列表见STL之vector函数详解
duque的各项操作只有以下几点和vector不同：
- deque不提供容量操作( capacity()、reserve() )
- deque提供push_front()、pop_front()函数直接操作头部
Deque的特点：
从deque的内部结构可知，deque元素是分布在一段段连续空间上，因此deque具有如下特点：
-
支持随机访问，即支持[]以及at()，但是性能没有vector好。
-
可以在内部进行插入和删除操作，但性能不及list。
由于deque在性能上并不是最高效的，有时候对deque元素进行排序，更高效的做法是，将deque的元素移到到vector再进行排序，然后在移到回来。
