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

我心飞翔 分类:javascript

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

TL;DR

栈的特点:先进后出。

常用来解决:

  • 括号有效性:遍历,遇左括号进栈,遇右括号,匹配则出栈,否则 false。遍历完,栈有值为 false,反之为 true
  • 下一个更大元素系列问题:倒着遍历,将下一个未知变成上一个已知,维护递减栈,也就是比栈顶小进栈,否则出栈
  • 最小栈:一般“以空间换时间”,使用辅助栈

循环数组:利用取余的技巧,没有实际扩充数组,但是遍历的时候,感觉像是在遍历循环数组。

练习:有效括号

stack_21

栈的特点就是:后进先出

对于有效性,由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶,遇到右括号就可以出栈,消消乐的感觉~

思路:遍历字符串,遇到左括号进栈,遇到右括号,和栈顶的元素不匹配直接是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

stack_22

这道题的暴力解法很好想到,就是对每个元素后面都进行扫描,找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O(n^2)。

下一个更大这类问题可以这样抽象思考:把数组的元素想象成并列站立的人,元素大小想象成人的身高。这些人面对你站成一列,如何求元素「2」的 Next Greater Number 呢?很简单,如果能够看到元素「2」,那么他后面可见的第一个人就是「2」的 Next Greater Number,因为比「2」小的元素身高不够,都被「2」挡住了,第一个露出来的就是答案。

stack_23

下一个更大元素系列问题:可以同一套思路和模板

  • 倒着遍历,将下一个未知变成上一个已知
  • 维护递减栈,遇见比栈顶大的,栈顶出栈,直到遇见比栈顶小的或者栈空,入栈
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

stack_24

这题比刚刚的题复杂在,循环数组上。

这类问题,其实稍微变化下思路就好~

[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;
};
 

练习:最小栈

stack_25

这里其实稍微麻烦一点的是,getMin,暴力法肯定容易,但是时间复杂度O(n),想变成O(1)。

换个栈思路,每次push的时候,除了存数据,还维护最小栈(辅助栈),栈顶就是当前数组的最小元素;pop的时候,栈顶元素弹出。

155_fig1.gif

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

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

官方动画题解

引用

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

回复

我来回复
  • 暂无回复内容