最近在看数据结构和算法,努力总结出道~
TL;DR
栈的特点:先进后出。
常用来解决:
- 括号有效性:遍历,遇左括号进栈,遇右括号,匹配则出栈,否则 false。遍历完,栈有值为 false,反之为 true
- 下一个更大元素系列问题:倒着遍历,将下一个未知变成上一个已知,维护递减栈,也就是比栈顶小进栈,否则出栈
- 最小栈:一般“以空间换时间”,使用辅助栈
循环数组:利用取余的技巧,没有实际扩充数组,但是遍历的时候,感觉像是在遍历循环数组。
练习:有效括号
栈的特点就是:后进先出
对于有效性,由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶,遇到右括号就可以出栈,消消乐的感觉~
思路:遍历字符串,遇到左括号进栈,遇到右括号,和栈顶的元素不匹配直接是false
,匹配的话出栈。遍历完之后,如果栈有元素,说明false
,反之为true
。
// 语义化更明确些
const top = (stack) => stack[stack.length - 1];
function isValid(s) {
let stack = [];
// 字典存放配对信息
let dict = {
"{": "}",
"[": "]",
"(": ")",
};
for (let i = 0; i < s.length; i++) {
let cur = s[i];
// 是不是左边括号
const isLeft = cur in dict;
// 左括号进栈
if (isLeft) stack.push(cur);
// 右括号,和栈顶看看是不是一对,是则出栈,不是则false
else {
const isPair = dict[top(stack)] === cur;
if (!isPair) return false;
stack.pop();
}
}
// 遍历完,栈里有元素则是false,反之是true
return !stack.length;
}
空间是 O(n),时间也是 O(n)
可以看下官方题解
练习:下一个更大元素 1
这道题的暴力解法很好想到,就是对每个元素后面都进行扫描,找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O(n^2)。
下一个更大这类问题可以这样抽象思考:把数组的元素想象成并列站立的人,元素大小想象成人的身高。这些人面对你站成一列,如何求元素「2」的 Next Greater Number 呢?很简单,如果能够看到元素「2」,那么他后面可见的第一个人就是「2」的 Next Greater Number,因为比「2」小的元素身高不够,都被「2」挡住了,第一个露出来的就是答案。
下一个更大元素系列问题:可以同一套思路和模板
- 倒着遍历,将下一个未知变成上一个已知
- 维护递减栈,遇见比栈顶大的,栈顶出栈,直到遇见比栈顶小的或者栈空,入栈
const top = (arr) => arr[arr.length - 1];
// [1,4,6,2] => {1:4,4:6,6:-1,2:-1}
var _nextGreaterElement = function (arr) {
// 递减栈
let stack = [];
// 答案存储,这个视不同题目而变化
let res = {};
// 倒着遍历
for (let i = arr.length - 1; i >= 0; i--) {
let cur = arr[i];
// 维护递减栈,遇见比栈顶大的,栈顶出栈,直到遇见比栈顶小的或者栈空,操作答案和当前值入栈
while (stack.length && cur >= top(stack)) {
stack.pop();
}
// 存储答案,这个视不同题目而变化
res[i] = stack.length ? top(stack) : -1;
stack.push(cur);
}
return res;
};
var nextGreaterElement = function (nums1, nums2) {
const res = _nextGreaterElement(nums2);
return nums1.map((item) => res[item]);
};
这样时间复杂度就是 O(m+n),空间复杂度也是 O(m+n)
单调栈解决 Next Greater Number 一类问题
练习:下一个更大元素 2
这题比刚刚的题复杂在,循环数组上。
这类问题,其实稍微变化下思路就好~
[1,4,3] => 循环数组的话 => [1,4,3,1,4,3]
但是不需要真的这样扩充数组,用下取余的小技巧,遍历的次数是两倍数组,但是 cur 的值就是arr[i%len]
然后依旧用上面的思路,但是,这里存储答案只需要在实际长度处开始存储即可。
const top = (arr) => arr[arr.length - 1];
var nextGreaterElements = function (nums) {
// 递减栈
let s = [];
// 这里视题目情况存储,此题用数组就可以
let ans = [];
const len = nums.length;
// 倒序遍历,数组长度变成2倍长了
for (let i = len * 2 - 1; i >= 0; i--) {
// 用取余运算计算当前值,表面看起来就像真的在遍历循环数组
let cur = nums[i % len];
while (s.length && cur >= top(s)) {
s.pop();
}
// 在实际数组的长度处,开始存储答案即可
i < len && (ans[i] = s.length ? top(s) : -1);
s.push(cur);
}
return ans;
};
时间复杂度和空间复杂度都是 O(n)~
单调栈解决 Next Greater Number 一类问题
快速试试:每日温度
请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
const top = (arr) => arr[arr.length - 1];
var dailyTemperatures = function (T) {
let s = [];
let res = [];
for (let i = T.length - 1; i >= 0; i--) {
const cur = T[i];
while (s.length && cur >= T[top(s)]) {
s.pop();
}
// 视情况而定,这里计算天数,显然存储i合适
res[i] = s.length ? top(s) - i : 0;
s.push(i);
}
return res;
};
练习:最小栈
这里其实稍微麻烦一点的是,getMin,暴力法肯定容易,但是时间复杂度O(n),想变成O(1)。
换个栈思路,每次push的时候,除了存数据,还维护最小栈(辅助栈),栈顶就是当前数组的最小元素;pop的时候,栈顶元素弹出。
function Stack(){
this.data = []
this.helpStack = []
}
Stack.prototype.push = num => {
this.data.push(num)
this.helpStack.push(num<this.data[this.data.length-1]?num:this.data[this.data.length-1])
}
Stack.prototype.pop = () => {
this.data.length && this.data.pop()
this.helpStack.length &&this.helpStack.pop()
}
Stack.prototype.getMin = () => {
return this.helpStack[this.helpStack.length-1]
}
当然这是同步栈的思路,不同步栈的,我个人觉得稍显复杂,有兴趣的可以继续研究~
官方动画题解
引用
- 修言的前端算法和数据结构
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!