【复试上机】LeetCode-简单-006-Valid Parentheses

6.Valid Parentheses

前言：

知识点课程说过，涉及到对称、反转、匹配的问题，一定要去考虑栈、递归。

文字思想：

我们这里用栈来解决。遇见左括号，入栈对应的右括号。所以栈内的右括号应该与遍历到的右括号相互抵消才对，具体步骤如下：

遇见左括号，入栈对应的右括号。

遇见右括号，出栈栈顶元素，看看是否一样。

 a)不一样：不匹配。

 b)一样。继续处理。

如果中途出现栈空：匹配失败。

遍历完毕之后，如果栈为空：匹配成功。

例子1：

待处理括号序列：{[]}

当前处理字符：{

待处理字符：[]}

栈内：

遇见{,将}入栈

当前处理字符：[

待处理字符：]}

栈内：

}

遇见[,将]入栈

当前处理字符：]

待处理字符：}

栈内：

]

}

当前栈不为空

遇见：], 栈顶元素为：]

当前处理字符：}

待处理字符：

栈内：

}

当前栈不为空

遇见：}, 栈顶元素为：}

最终栈为空

匹配：true

例子2：

待处理括号序列：{[)}

当前处理字符：{

待处理字符：[)}

栈内：

遇见{,将}入栈

当前处理字符：[

待处理字符：)}

栈内：

}

遇见[,将]入栈

当前处理字符：)

待处理字符：}

栈内：

]

}

当前栈不为空

遇见：), 栈顶元素为：],不相等

匹配不成功

代码：

复杂度：

时间复杂度：O(s.length)。

空间复杂度：使用到了栈，O(s.length)。

积累：

括号匹配问题，可以用栈。这种解法与我们讲数据结构知识点时候的解法不一样，而且这个解法更加的简便好懂，非常nice。

关于匹配、对称、反转要想到用栈。

整体。