日期：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，但其實(shí)并不hard贩据。對于這樣的括號匹配問題，很容易想到使用棧結(jié)構(gòu)较性。
class Solution {
public:
int longestValidParentheses(string s) {
//初始化變量鲤孵，建了一個相同長度的bool型數(shù)組壶栋，如果配對了的元素，該位置為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數(shù)組兩個相應(yīng)的位置置1.
a[myStack.top()] = true;
myStack.pop();
a[i] = true;
}
}
}
//最后還要遍歷一下bool型數(shù)組普监，看看最大的連續(xù)的長度是多少
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;
}
};
我的思路寫在了注釋中贵试。這樣的時間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)凯正，因?yàn)槎嚅_了一個數(shù)組毙玻。
我的用時是8ms，看了第一名的答案廊散，用時4ms淆珊，他使用了雙端隊(duì)列：
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;
}
};
其實(shí)思路是一樣的，不過在此還是復(fù)習(xí)一下雙端隊(duì)列吧奸汇。另外明天把STL容器和迭代器相關(guān)的知識一起復(fù)習(xí)一下。
Deque結(jié)構(gòu)
如圖1是deque的邏輯結(jié)構(gòu)往声，從表面上看擂找，deque具有連續(xù)性的存儲空間，并支持隨機(jī)存取功能浩销。實(shí)際上deque并不是我們所看到的樣子贯涎，其內(nèi)部結(jié)構(gòu)，如圖2所示慢洋。
deque在實(shí)現(xiàn)上主要有以下兩點(diǎn)：
由一段一段的定量連續(xù)空間構(gòu)成塘雳，第一個區(qū)塊朝某個方向擴(kuò)展，最后一個區(qū)塊朝相反方向擴(kuò)展普筹；
管理這些分段的定量連續(xù)空間败明，維護(hù)其整體連續(xù)的假象，并提供隨機(jī)存取的接口太防；
Deque的能力
與vector相比妻顶，deque功能上的不同之處在于：
- 首尾兩端都能快速的安插、刪除元素蜒车，因此需要在兩端安插讳嘱、刪除元素時，最好采用deque酿愧。
- 存在元素時沥潭，deque的內(nèi)部結(jié)構(gòu)會多一個間接過程，操作元素的效率會比vector低一些嬉挡。
- 迭代器需要在不同區(qū)塊間跳轉(zhuǎn)钝鸽，所以必須是特殊的智能指針汇恤，非一般指針。
- deque不支持對容量和內(nèi)存重分配時機(jī)的控制寞埠，除了首尾兩端安插屁置、刪除元素外，其他地方安插仁连、刪除元素都將導(dǎo)致元素的pointer蓝角、reference、iterator失效饭冬。不過使鹅，deque的內(nèi)存重分配機(jī)制優(yōu)于vector，因?yàn)閐eque不必在內(nèi)存重分配時復(fù)制所有的元素昌抠。
- deque的內(nèi)存區(qū)塊不再被使用時患朱，會被釋放。
Deque的操作函數(shù)：
Deque的操作函數(shù)和vector操作函數(shù)基本一模一樣炊苫，操作函數(shù)列表見STL之vector函數(shù)詳解
duque的各項(xiàng)操作只有以下幾點(diǎn)和vector不同：
- deque不提供容量操作( capacity()裁厅、reserve() )
- deque提供push_front()、pop_front()函數(shù)直接操作頭部
Deque的特點(diǎn)：
從deque的內(nèi)部結(jié)構(gòu)可知侨艾，deque元素是分布在一段段連續(xù)空間上执虹，因此deque具有如下特點(diǎn)：
支持隨機(jī)訪問，即支持[]以及at()唠梨，但是性能沒有vector好袋励。
可以在內(nèi)部進(jìn)行插入和刪除操作，但性能不及l(fā)ist当叭。
由于deque在性能上并不是最高效的茬故，有時候?qū)eque元素進(jìn)行排序，更高效的做法是蚁鳖，將deque的元素移到到vector再進(jìn)行排序磺芭，然后在移到回來。
