遇到括号有效性、下一个更大元素、特定的最小值，尝试栈
最近在看数据结构和算法，努力总结出道~
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] }
当然这是同步栈的思路，不同步栈的，我个人觉得稍显复杂，有兴趣的可以继续研究~
