字节跳动这家公司，应该是所有秋招的公司中，对算法最重视的一个了，每次面试基本都会让你手撕算法，今天这篇文章就记录下当时被问到的几个算法题，并且每个算法题我都详细着给出了最优解，下面再现当时的面试场景。看完一定让你有所收获
一、小牛试刀：有效括号大部分情况下，面试官都会问一个不怎么难的问题，不过你千万别太开心，因为这道题往往可以拓展出更多有难度的问题，或者一道题看起来很简单，但是给出最优解，确实很不容易的。这道题是这样的
给定一个只包括 '('，')'的字符串，判断字符串是否有效。注：空字符串属于有效字符串
示例 1: 输入: "(())" 输出: true 实例 2： 输入: "())(" 输出: false第一眼看到这道题，我去，这么简单，稳了（因为一面的时候，刚刚被面试官怼过勇者斗恶龙的DP题，在 leetcdoe 属于 hard 级别）。
其实这道题的 leetcode 第 20 题的简化版，属于 easy 级别
于是我也不假思索直接用栈来解决了，相信 99% 都会用栈解决吧？这里我稍微说以下过程吧，步骤如下：
1、在遍历字符串的过程中，遇到 "(" 就让它入栈，遇到 ")" 就判断下栈里面有没有 "(" ：
（1）、如果有，则把处于栈顶的 "(" 弹出，相当于和 ")" 进行匹配，然后继续往后遍历字符串 （2）、如果没有，则匹配失败。相当于字符串的最前面出现了 ")"，显然这是不合理的。2、当字符串遍历完成，判断栈是否为空，如果为空则表示字符串有效，否则无效。
为了兼顾小白，我该给你们画了个图演示，，，，我太良心了。
代码如下所示（Java，不过不是学Java也能看懂）
public static boolean isValid(String s){ if(s == null || s.length() < 1) return true; int n = s.length();// 字符串长度 // 创建一个栈来装字符 Stack<Character> stack = new Stack<>(); // 遍历字符串 for(int i = 0; i < n; i++){ // 获取字符串的第 i 个字符 char c = s.charAt(i); if(c == '('){ stack.push(c); }else{ if(stack.isEmpty()) return false; else stack.pop(); } } // 判断是否为空 if(stack.isEmpty()) return true; return false; } 二、优化接着面试官说我这道题的空间复杂度是 O(n)，问我能优化一下吗？
说实话，如果你做过 leetcode 的第 20 题，可能你的脑子会被定向也不一定，因为那道题用栈来处理就是最优解的了。不过这道题属于简化版，其实可以把空间复杂度优化成 O(1)，大家可以想一下哦。
由于我们栈里面存放的都是同一种字符 "(" ，其实我们可以用一个变量来取代栈的，这个变量就记录 "(" 的个数，遇到 "(" 变量就加 1，遇到 ")" 变量就减 1，栈为空就相当于变量的值为 0。
当时脑子有点不知为啥，就马上相当这个方法了，于是一分钟就修改好了代码，如下：
public static boolean isValid(String s){ if(s == null || s.length() < 1) return true; int n = s.length();// 字符串长度 // 用来记录遇到的 "(" 的个数 int sum = 0; // 遍历字符串 for(int i = 0; i < n; i++){ // 获取字符串的第 i 个字符 char c = s.charAt(i); if(c == '('){ sum++; }else{ if(sum == 0) return false; else sum--; } } return sum == 0 ? true : false; }这样子的话，时间复杂度为 O(n)，空间复杂度为 O(1)。
三、最长有效括号接着面试官就继续就这道题继续加大难度，问题改为如下
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"其实这道题就是 leetcode 的原题，第 32 题，难度为 hard。
这道题由于我之前做过，微微一笑，假装用严肃的表情思考一下，然后马上给出了思路，刚开始我是用暴力法的。
1、暴力法
暴力法其实很简单，就是最开始把第一个字符当做最长有效括号的首字符来遍历字符串，接着把第二个字符当做最长有效括号的首字符来遍历字符串，接着把第三个字符......
例如对于 s = "( ) ) ( ( ) )"。
把第一个字符作为首字符，则 max = 2 （遇到第三个字符 ')' 就匹配不了了）
把第二个字符作为首字符，则 max = 0 （一开始就是 ')'，显然啥也匹配不了）
把第三个字符作为首字符，则 max = 0
把第四个字符作为首字符，则 max = 4
.....
这种做法的时间复杂度为 O(n^2)，空间复杂度为 O(1)
基本上面那道题一样，只是做了 n 次遍历。
接着面试官问，还能优化吗？
早就知道会问优化的了，我自己之前也做过这道题，于是假装思考了一下，马上给出了优化。
2、优化
这道题的优化版本我们仍然是用栈来做，不过入栈的时候，不是让 "(" 入栈，而是让 "(" 的下标入栈。步骤如下：