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、优化

这道题的优化版本我们仍然是用栈来做，不过入栈的时候，不是让 “(” 入栈，而是让 “(” 的下标入栈。步骤如下：

1、先把 -1 放入栈内。（至于为什么？看到后面你就知道了） 2、、对于遇到的每个 ‘(’ ，我们将它的下标放入栈中。 3、对于遇到的每个 ‘)’ ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。

通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。

看不懂？没事，我弄个例子画几个图，例如 s = “( ) ) ( ( ) )”，并且用变量 max 来保存最长有效字符串的程度，i 表示当前字符串的下标

0、初始化：max = 0; i = 0。-1 放入栈内

1、i = 0，s[i] = ‘(’，下标 i = 0 入栈

2、i = 1，s[i] = ‘)’，出栈; i - 栈顶元素 = 1 - (-1) = 2，此时 max = 2

3、i = 2，s[i] = ‘)’，出栈；这个时候要注意：由于 -1 出栈后，栈顶没有元素了，所以这个时候我们必须把 ‘)’ 的下标入栈，相当于最开始的初始化。

4、i = 3，s[i] = ‘(’，入栈;

5、i = 4，s[i] = ‘(’，入栈;

6、i = 5，s[i] = ‘)’，出栈；i - 栈顶 = 5 - 3 = 2；此时 max = 2;

7、i = 6，s[i] = ‘)’，出栈；i - 栈顶 = 6 - 2 = 4；此时 max = 4;

8、遍历结束，最长有效括号为 4。

看不大懂？没事，看下代码加深理解勒，代码如下：

public int longestValidParentheses(String s) {

int max = 0;

Stack stack = new Stack<>();

stack.push(-1);

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == ‘(’) {

//下标入栈

stack.push(i);

} else {

// 出栈

stack.pop();

// 看栈顶是否为空，为空的话就不能作差了

if (stack.empty()) {

stack.push(i);

} else {

// i - 栈顶，获得档期有效括号长度

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Java）

本次面试答案，以及收集到的大厂必问面试题分享：

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Java）
[外链图片转存中…(img-2VB4KNIF-1712761262080)]

本次面试答案，以及收集到的大厂必问面试题分享：

[外链图片转存中…(img-ByZjtL1X-1712761262080)]

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
[外链图片转存中…(img-rG06Xn4t-1712761262081)]