在代码的世界中,无论是什么语言,栈其实都是一种非常重要的数据结构。
全球闻名的代码提问社区stack overflow就以栈(stack)溢出作为网站名的一个部分。
在写代码或者是debug的过程中,相信你已经感受到了在函数调用栈的世界蹦蹦跳跳的快乐了。
在学校里刷oj,刷LeetCode,进入社会参加笔试面试的过程中,相信你也感受到了栈的强大和易用。
这篇博文非常适合数据结构基础非常薄弱的同学食用,也欢迎基础扎实的同学指正和交流。
如果从未感受过stack的美妙和强大,这篇博文将非常适合你~
什么是栈?
JavaScript中的Array与栈
leetcode 栈 解法题目
面试题 栈 解法题目
下面这个结构大家都熟悉,瞬间体现出栈LIFO的特性。
// 定义一个栈 let stack = [1,2,3]; // 入栈 stack.push(4); // stack [1,2,3,4] // 出栈 stack.pop(); // 4 stack [1,2,3]
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
var MinStack = function() { this.stack = []; }; MinStack.prototype.push = function(x) { this.stack.push(x); }; MinStack.prototype.pop = function() { return this.stack.pop(); }; MinStack.prototype.top = function() { return this.stack[this.stack.length - 1]; }; MinStack.prototype.getMin = function() { return Math.min(...this.stack); };
题目:https://leetcode-cn.com/probl...
解法:https://github.com/FrankKai/l...
题目:https://leetcode-cn.com/probl...
题解:https://github.com/FrankKai/l...
/** * 解法2:栈 * 1.构建一个栈 * 2.依次入栈所有开括号 * 3.遇到闭括号时与栈顶的开括号匹配 * 3.1若匹配上,出栈并继续 * 3.2匹配不上,return false * 4.遍历结束后的栈应该为空,否则为无效括号 */ var isValid = function(s) { var bracketsMap = { "(": ")", "{": "}", "[": "]" }; var openBrackets = Object.keys(bracketsMap); var closeBrackets = Object.values(bracketsMap); var stack = []; var sArr = s.split(""); for (var i = 0; i < sArr.length; i++) { if (openBrackets.indexOf(sArr[i]) !== -1) { stack.push(sArr[i]); } else if (closeBrackets.indexOf(sArr[i]) !== -1) { var top = stack[stack.length - 1]; if (sArr[i] === bracketsMap[top]) { stack.pop(); } else { return false; } } } return stack.length === 0; }
/** * @param {string} a * @param {string} b * @return {string} */ var addBinary = function (a, b) { /** * 解法2:栈 * 时间复杂度:O(n) * 性能:56ms, 35.5MB */ let aArr = a.split(""); let bArr = b.split(""); let stack = []; let count = 0; while (aArr.length !== 0 || bArr.length !== 0) { let aPop = aArr.pop() || 0; let bPop = bArr.pop() || 0; let stackBottom = 0; if (stack.length > count) { stackBottom = stack.shift() || 0; } let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom) if (sum <= 1) { stack.unshift(sum); } else { stack.unshift(sum - 2); stack.unshift(1); } count++; } return stack.join(""); };
题目:https://leetcode-cn.com/probl...
题解:https://github.com/FrankKai/l...
/** * @param {number[]} A * @return {number[]} */ var sortArrayByParity = function (A) { /** * 栈头栈尾解法即可 * 偶数栈底推入unshift * 奇数栈顶推入push */ var stack = []; for (var i = 0; i < A.length; i++) { if (A[i] % 2 === 0) { stack.unshift(A[i]); } else { stack.push(A[i]); } } return stack; };
题目:https://leetcode-cn.com/probl...
题解:https://github.com/FrankKai/l...
/** * @param {number[][]} intervals * @return {number[][]} */ var merge = function (intervals) { /** * 解法1:排序 + 栈 * 性能:88ms 36.3MB * 思路: * 推入区间 空栈 或者 arr[0]大于栈最后一个区间闭 * 覆盖重叠 arr[0]小于栈最后一个区间闭 * */ intervals.sort((a, b) => a[0] - b[0]); let stack = []; for (let i = 0; i < intervals.length; i++) { let currrentInterval = intervals[i]; let stackLastItem = stack[stack.length - 1]; if (stack.length === 0 || currrentInterval[0] > stackLastItem[1]) { stack.push(currrentInterval); } else if (currrentInterval[0] <= stackLastItem[1]) { stackLastItem[1] = Math.max(stackLastItem[1], currrentInterval[1]); } } return stack; };
题目:https://leetcode-cn.com/probl...
题解:https://github.com/FrankKai/l...
var sortColors = function (nums) { /** * 解法1:递归 栈 * 性能:64ms 35.1MB */ var length = nums.length; var countHead = arguments[1] || 0; var countTail = arguments[2] || 0; for (var i = countHead || 0; i < length - countTail; i++) { if (nums[i] === 0) { countHead++; nums.unshift(nums.splice(i, 1)); // 增加if(i!==0)会降低10ms性能 return sortColors(nums, countHead, countTail); } else if (nums[i] === 2) { countTail++; nums.push(nums.splice(i, 1)); return sortColors(nums, countHead, countTail); } } return nums; }
题目:https://leetcode-cn.com/probl...
题解:https://github.com/FrankKai/l...
/** * @param {number[]} nums * @return {string[]} */ var summaryRanges = function (nums) { /** * 解法1:排序 + 栈 * 性能:52ms 33.7MB */ nums.sort((a, b) => a - b); let stack = []; let result = []; for (let i = 0; i < nums.length; i++) { if (stack.length === 0 || nums[i] - stack[stack.length - 1] === 1) { stack.push(nums[i]); } else { stackToResult(); stack = []; stack.push(nums[i]); } if (i === nums.length - 1) { stackToResult(); } } function stackToResult() { if (stack.length > 1) { result.push(`${stack[0]}->${stack[stack.length - 1]}`); } else { result.push(`${stack[0]}`); } } return result; };
题目:https://leetcode-cn.com/probl...
题解:https://github.com/FrankKai/l...
/** * 解法2:栈 + 递归 1132ms 19.96% 59.2MB 11.76% * 思路: * 1.通过shift取出栈底元素 * 2.遍历剩余温度栈内温度 * 若温度出现比栈底温度大者 * 存储i+1 * 递归进行下一次入栈 * 若温度小于等于栈底温度 * 若遍历到最后一个都没有出现更大的 * 存储 0 * 进行下一次入栈 * 3.最后一个温度无论如何都肯定是0 */ var dailyTemperatures = function(T) { if (T.length < 1 || T.length > 30000) return false; var result = arguments[1] || []; var bottom = T.shift(); for (var i = 0; i < T.length; i++) { var t = T[i]; if (t > bottom) { result.push(i + 1); return dailyTemperatures(T, result); } else { if (i === T.length - 1) { result.push(0); return dailyTemperatures(T, result); } } } result.push(0); return result; }
实现大整数相加,大于 Number.MAX_VALUE,不能直接使用 BigInt。
/** * 请通过代码实现大整数(可能比Number.MAX_VALUE大)相加运算 // your code goes here var bigint1 = new BigInt('1231230'); var bigint2 = new BigInt('12323123999999999999999999999999999999999999999999999991'); console.log(bigint1.plus(bigint2)) */
function BigInt(value) { this.value = value; } BigInt.prototype.plus = function (bigint) { let aArr = this.value.split(""); let bArr = bigint.value.split(""); let stack = []; let count = 0; while (aArr.length !== 0 || bArr.length !== 0) { let aPop = aArr.pop() || 0; let bPop = bArr.pop() || 0; let stackBottom = 0; if (stack.length > count) { stackBottom = stack.shift(); } let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom); if (sum < 10) { stack.unshift(sum); } else if (sum >= 10) { stack.unshift(sum - 10); stack.unshift(1); } count++; } return stack.join(""); };
期待和大家交流,共同进步,欢迎大家加入我创建的与前端开发密切相关的技术讨论小组:
- 微信公众号: 生活在浏览器里的我们 / excellent_developers
- Github博客: 趁你还年轻233的个人博客
- SegmentFault专栏:趁你还年轻,做个优秀的前端工程师
- Leetcode讨论微信群:Z2Fva2FpMjAxMDA4MDE=(加我微信拉你进群)
努力成为优秀前端工程师!