【leetcode刷题笔记】032.Longest Valid Parentheses

日期：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再进行排序，然后在移到回来。

最后编辑于：2018.09.15 00:44:37