面试中遇到这道算法题，你能答对吗？（送10元现金红包）

有许多读者在后台给我留言，说自己即将面临毕业或者换工作，希望可以多为他们分享一些面试相关知识。

其实，大多数公司在面试时都尤为看中候选人的算法能力，他们甚至会让候选人当场写代码，我认识一位Stony Brook University的朋友，应聘亚马逊，上来就是3道LeetCode题。公司为什么喜欢先来算法题并现场写代码呢？因为算法能力也会直接反映出一个程序员水平的高低。

今天，就用一道经典面试题为例，给大家分享前 Facebook 面试官的解题思路，哪怕你暂时不需要面试，也可以通过培养算法思维，提升工作效率。

LeetCode 第 20 题：判断括号是否合法 https://leetcode-cn.com/problems/valid-parentheses/description/

2

你能5分钟内准确无误地写出这道题的代码吗？ 不管有没有把握，都可以看下面的详细分析，带有清晰的示意图。最为关键的是，本题至少有两种解法，只需要不到 10 行的代码，不妨仔细读一下！

我们先来看题干：给定一个字符串，这个字符串里面只包含大中小括号，让你判断这个字符串是否合法，所谓的括号合法指的就是左括号和右括号必须匹配，同时也允许嵌套的情况。

具体规则如下：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。如果觉得规则比较抽象，那我们就来看几个简单的例子：

"()" "()[]" "([)]" "((([]))" "]][["

第一种情况 "()" 比较简单，就是左小括号和右小括号，显然可以配对，所以是合法的。

第二种情况 "()[]" 就是多了一对中括号，所以也是合法的。

我们再看第三种情况 "([)]" ，在第二个例子的基础上，这里把中间的两个括号调换了一下位置，这样一来，左中括号和右小括号就无法进行匹配的，即左小括号和左中括号都没有以正确的顺序闭合，显然就不合法了。

第四种情况是一组嵌套括号 "((([]))"，最左边是 3 个左小括号，最右边有 2 个右小括号，中间则是一对相匹配中括号，由于最右边的右小括号只有两个，无法和左边的 3 个一一匹配，所这个也是不合法的。但是如果把最右边的小括号增加一个，变成"((([])))"，这样就合法了。

第五种情况 "]][[" ，一开始出现的就是一个右括号，没有左括号与之匹配，显然不合法。

那么这个题目应该怎么做呢？

这是一个比较经典的面试题，用到的也是比较经典的数据结构，就是用“栈”来解决这个问题，我们来看看具体该怎么做。

首先，我们把栈画出来是下面这个样子的：

然后我们按照从左到右的顺序依次把字符串中的括号放到这个栈里面。

如果第一个进来的是左括号，对于这种情况，我们现在没法判断它是否合法，还需要后续看有没有相应的右括号和它匹配。那我们就先把它留着，留着的意思就是把左括号先放在栈底去存着的，也就是压入栈（push）。

如果是右括号先进来呢？因为右括号不能独立存在的，如果一上来就直接来个右括号，那显然就不合法了。所以右括号要进来的时候，要查看（peek）当前栈顶是否有相应的左括号与之相匹配。如果是右小括号，那就看一下栈顶是否有左小括号，如果是右中括号，就看一下栈顶是否有左中括号。

如果当前栈顶有与之相匹配的左括号的话，那就要把这个栈顶元素给推（pop）出去了，如果不匹配的话，就直接返回不匹配。

最后还有一点要注意的就是，这个流程全部走完一遍后，如果字符串里面的括号是一一匹配的，那么最后这个栈本身应该是空的。我们可以用之前的 5 个例子来验证一下。

首先第一个字符串"()"，左小括号"("进来之后先把它压入到栈底。

然后要进来的是右小括号"）"，此时我们就要查看（peek）当前栈顶的元素是不是和这个右小括号相匹配的，这种情况下刚好是匹配的，那么就把这个元素"（"从栈里面推出（pop）。

然后这个字符串的全部流程就走完了，现在我们可以看到这个栈为空，这就说明这个字符串里面的括号都是相匹配的，大家都很幸福的配对在一起了，当然也就说明是合法的。

第二个情况"()[]"也类似，只不过多重复了一对中括号的匹配流程，就不再赘述了。

来看第三种情况"([)]"，一开始左小括号"("进来，先压入栈底，然后左中括号"["也进来，依然是把它留在栈中。

然后就来到右小括号")"，这时我们一查找，发现当前栈顶元素是左中括号"[", 它和右小括号")"没法进行匹配，这种情况就可以直接返回不合法这个结果了。

第四种情况"((([]))"，前四个元素"(((["都是左括号，所以都要进行压栈操作。

这时候到第五个元素右中括号"]"要进来，查看当前栈顶元素"["，正好相匹配，于是把左中括号"["从栈顶推出（pop），接下来同理，剩下的两个右小括号也能和栈里面的左小括号匹配，整个字符串走完一遍之后，我们发现最后的的栈不为空，还剩一个未被匹配的左小括号"("在里面。所以这种情况也是不合法的。

最后一种情况"]][["更简单，一开始就是一个右括号，那我们直接返回不合法就可以了。

最后我们来算一下，用这种办法进行判断的话，它的时间复杂度和空间复杂度是多少呢？

首先，每一个元素进栈和出栈的操作是 O(1) 的，也就是一次性的操作，那么每一个元素都会进这个栈一次，而且仅进入一次，所以就是 O(n) 的时间复杂度。

它的空间复杂度也是一样的道理，最坏的情况下，所有元素都会压在这个栈里面，所以它在空间上也是 O(n) 的复杂度。

接下来我们来看代码。

首先要说明的是，大部分人在写这道题的代码的时候，稍微不注意就可能写得很冗余、很复杂，这样在面试中可能就会扣掉一些分数。

那我们来看一段比较优秀的代码：

首先，第三行这里用了一个比较高级的处理方式，就是用一个字典来把左右括号的对应关系存起来。同时，这里还有一个比较有趣的技术处理，就是所有的右括号放在前面，也就是作为字典的 key，接下来我们可以看到它这么做的一个好处是什么。

再看下面的代码，根据我们之前讲的思路，先对字符串 s 中的元素 c 进行遍历，如果这个 c 不在我们定义的这个字典 paren_map 中，就说明它不是右括号，而是一个左括号，不管是左中括号好也好，还是左小括号也好，只要是左括号，按照之前所说的处理思路，我们就把这个 c 放在栈里面去。

如果 c 在 paren_map 里面的话，就说米 c 是右括号，那我我们首先要做的就是判断当前的栈是否为空，如果为空，就返回 false，如果不为空，我们就看这个右括号能否和当前栈顶元素相匹配，如果不匹配，也返回 false。

最后，如果匹配流程都走完一遍之后，最后我们还要判断什么？就是判断最终这个栈是否不为空，也就是这段代码的最后一行。

如果最终的栈不为空的话，说明是不合法法的，如果为空的话，则是是合法的。

整体的代码建议大家多看一下，最好能和自己写的代码做一下对比，看看自己的代码还有哪些可以优化的地方。

我们再来看看这道题的另外一种写法：

这种写法我从两个方面来进行分析。

第一，这段代码第一眼看上去会觉得比较简洁，看起来也比较漂亮。

我们再仔细看它的逻辑，会发现它的逻辑也很简单。关键逻辑就在第 5 行：如果这个字符串里面有相邻的左右匹配的括号，就把它消除掉，一直重复这个过程，如果到最后这个字符串可以为空，就说明它里面的所有括号都匹配成功了，也就说明是合法的，否则就不合法了。

这样写的话，逻辑比较直接，代码看起来也挺漂亮，但是它有一个问题，就是它的时间复杂度不好判断，它的时间复杂度在平均的情况下会达到二分之 N 平方的时间复杂度，也就是说相比起一开始用的栈这种方法，它在时间复杂度方面要略差一点。

在这种情况下，即使你的代码看起来是比较漂亮，但如果碰到有经验的面试官，看到你的时间复杂度其实是更差的，那就会在面试中被减掉一定的分数。

至此，如果您仔细学习了这道题的两种解法的话，相信已经收获满满。如果有兴趣，不妨继续看下去，更精进一步。