遇到括号有效性、下一个更大元素、特定的最小值，尝试栈

最近在看数据结构和算法，努力总结出道~

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]
}
 

当然这是同步栈的思路，不同步栈的，我个人觉得稍显复杂，有兴趣的可以继续研究~

官方动画题解

引用

• 修言的前端算法和数据结构