一、20. 有效的括号
题目链接:
学习前:
思路:
-
当前元素为左括号,直接入栈
-
当前元素为右括号,若找到对应的左括号匹配,则循环继续;反之返回false
-
若栈为空,返回true;反之false
时间复杂度:O(n)
空间复杂度:O(n)
学习后:
采用入栈右括号,降低复杂度。即当遇到左括号,入栈对应的右括号;遇到右括号,与栈顶元素直接进行比较
二、1047. 删除字符串中的所有相邻重复项
题目链接:
学习前:
思路:
用一个栈存放删除后的字符串,接着出栈并翻转
时间复杂度:O(n)
空间复杂度:O(n)
学习后:
还可以采取快慢指针和字符串直接作为栈的思路
三、150. 逆波兰表达式求值
题目链接:
学习前:
思路:
用栈存储表达式,当遇到数值时入栈,当遇到运算符时弹出两个数进行运算后入栈
时间复杂度:O(n)
空间复杂度:O(n)
学习后:
最后栈内只剩一个元素,最好将这个元素出栈,便于进行内存回收
四、学习总结
- 时间:2h
- 对栈这种数据结构的应用,注意内存问题
- 比较String对象的值是否相等时,不能直接用==,应当用equals