最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 遇到括号有效性、下一个更大元素、特定的最小值,尝试栈

    正文概述 掘金(颜酱)   2021-04-07   92

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

    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介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元