Loop

Loop

Man | WebDeveloper | GISer

栈刷题记录

Date:

栈刷题记录

栈

155.最小栈

  • 描述：实现一个栈，支持push, pop, top操作，支持线性时间getMin()
  • 实现：用两个栈，一个栈是正常栈，另一个最小值栈，最小值栈的栈顶元素是当前栈的最小值
  • 注意：需要同步push和pop，对于最小值栈来说pop是直接pop，但是push需要push最小值

227.基本计算器II

  • 描述：实现计算器，包括加减乘除，如3+2*2
  • 实现：用两个栈，一个num栈，一个op栈
    • 遍历字符
    • 遇到空格跳过
    • 遇到数字则累计num = num * 10 + parseInt(char, 10), 因为数字可能不止一位
    • 遇到运算符，考虑优先级，可能要pop进行计算后，再入栈计算结果和运算符
      • 如遇+ -，因为加减优先级最低，所以把栈中的东西都一一pop出来计算，最后再把结果和运算符入栈
      • 如遇* /，因为乘除优先级最高，栈中的运算优先级只会<=乘除，所以直接入栈
    • 最终，把栈中的数字和运算符一一pop出来计算，得到最终结果

232.用栈实现队列

  • 实现：用两个栈，一个inStack，一个outStack
    • 入队时，直接入inStack
    • 出队时，如果outStack为空，则把inStack中的元素全部pop出来，并push到outStack中，再pop outStack的栈顶元素
    • 出队时，如果outStack不为空，则直接pop outStack的栈顶元素

394.字符串解码

  • 描述：给定一个编码后的字符串，如3[a2[c]]，解码后得到accaccacc
  • 实现：用两个栈，一个num栈，一个str栈，注意str栈存的是前一个str
    • 遍历字符，遇数累计数num，遇字符累计字符curStr
    • 遇到[，把num和curStr入栈，并重置num和curStr
    • 遇到]，把栈顶的num和curStrpop出来，把curStr重复num次，然后和栈顶的str拼接得到新的curStr
      394

946.验证栈序列

  • 描述：给一个pushed和popped，判断是否是合法的栈序列
  • 实现：用一个栈，遍历pushed，push到栈中，然后while循环，如果栈顶元素和popped的当前元素相等，则pop栈顶元素，最后判断栈是否为空

单调栈

单调栈适用场景

求某个元素左边/右边第一个比它大/小的元素，时间复杂度O(n)

例如： 求左侧比X大的元素

  • 从左到右遍历，单调栈（从栈底0到栈顶单调递减）
  • 当X入栈的时候，栈顶元素就是X左侧第一个比它大的元素，如果插入时栈空，则X左侧没有比它大的元素
  function monoIncreaseStack(arr) {
    // 创建一个从0到栈顶递增的栈
    const stack = []

    for(let item of arr){
      // 在插入元素之前，while栈顶元素比它大，则弹出栈顶元素, 再插入, 最终就可以得到从0到末尾递增的序列
      while(stack.length && stack[stack.length - 1] > item){
        stack.pop()
      }
      stack.push(item)
    }
  }

496.下一个更大元素I

  • 描述： 给定两个数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
  • 实现：
    • 遍历nums2，用单调栈得到每个元素的下一个更大元素, 并存储在表中
    • 遍历nums1，用读表获取结果，读不到就是-1
  • 注意： 找比它大的数，我的做法是构建从0到末尾是单调递减的单调栈，每当遇到大于栈顶的数，就记录为栈顶元素的下一个更大元素，然后弹出栈顶元素

739.每日温度

  • 描述： 给定一个数组，每个元素表示每天的温度，求每天需要等几天才能等到更暖和的一天，返回数组。
  • 实现：
    • 遍历温度数组，构建自0到末尾递减的单调栈，当遇到大于栈顶的温度时，弹出栈顶，记录diff
  • 注意：
    • 上一题是用一个dict把结果保存起来，二次再循环去查
    • 其实可以一次性做好，stack存的是index
    • while temperatue[stack[stack.length - 1]] < temperature[i]
    • const id = stack.pop()
    • ans[id] = i - id

503.下一个更大元素II

  • 描述：给定一个数组, 这是一个环形数组，求每个元素的下一个更大元素，返回数组。
  • 注意：所谓环形数组，其实可以把数组copy一份放在末尾，就把环形数组变成一般数组了，这个copy可以只是下标，用i % arr.length遍历
  • 实现：本题和739类似滴，stack里存index即可

901.股票价格跨度

  • 描述：类似的，给数组，给一个方法next(price)，返回当前加个之前小于等于它的个数
  • 注意：
    • 要找在它之前小于等于它的个数，相当于是找左侧第一个比它大的数，然后返回index差
    • 为了少存一个priceList，可以让stack中的元素为[price, index]
  • 实现：
    • 在next方法中（插入新元素时）
    • while stack[stack.length - 1][0] <= price
      • pop出栈顶元素
    • 如果栈空，说明在这之前没有比它大的，返回index + 1
    • 否则，返回index - stack[stack.length - 1][1]

316. 去除重复字母

  • 描述：有点抽象，给一个字符串，要求返回一个字符串，要求返回的字符串中每个字母只出现一次，并且按照字典序排序
  • 注意：
    • 每个字母只出现一次，在单调栈场景下，应该注意每个字母都要保留，意味着pop的时候要加条件
    • 字典序排序，在js中，'a' - 'b', 'a' - '0'都是NaN，所以需要用'a'.charCodeAt(0) - 'b'.charCodeAt(0)来比较字符串大小
    • 本题关键是，每个字母都要保留，是有所额外条件的单调栈
  • 实现:
    1. 遍历字符，统计出现次数
    2. 遍历字符，按条件构建单调栈，对于每个字符c
      • c 如果在栈中，c的次数减1，跳过
      • c 如果不在栈中
      • while stack有元素 栈顶元素字典序大于c 栈顶元素出现次数大于0，符合条件那就pop
      • 最后把c入栈
      • 最后把c的次数减1