栈和队列

简单说明

对于js中的Array 栈

push() 进栈
pop() 出栈队列
push() 进队列
shift() 出队列

232 用栈实现队列

🖐️ 无需多言，两个栈实现

使用两个栈来实现队列的功能。
栈1用于入队，栈2用于出队。
当需要出队时，如果栈2为空，则将栈1中的元素全部弹出并压入栈2。
然后从栈2中弹出元素作为出队结果。

225. 用队列实现栈

思路1 - 用两个队列
1. 队列1用于入栈，队列2用于出栈。
2. 当需要出栈时，如果队列1中只有一个元素，则直接弹出该元素作为出栈结果。
3. 如果队列1中有多个元素，则将队列1中的所有元素依次出队并入队到队列2中，直到队列1只剩下一个元素。
4. 然后将队列1中的最后一个元素弹出作为出栈结果。
思路2 - 一个队列
1. 当需要出栈时，将队列中的n-1个元素出队并入队到自身，直到队列中只剩下一个元素。
2. 然后弹出最后一个元素作为出栈结果。

20. 有效的括号

🖐️ 无需多言, 栈遇左括push右括号，遇右括号pop匹配

150. 逆波兰表达式求值

🖐️ 无需多言, 栈遇到操作符时，pop b, pop a，然后 oprate(a, b) 注意：

先b后a
除法的分母
除法的靠0取整，用 | 0

🌟 239. 滑动窗口最大值

这个就比较吊了，用到了优先队列。

一开始在做这题的时候，总是很难受，想着用一个队列作为窗口，滑动的时候无非就是头部出队尾巴入队，但是如果你想记录窗口内的最大值，你不知道这个最大值是否是第一个元素，或者是中间和末尾的元素，这就导致更新窗口之后，需要再遍历窗口求MAX，这样就超时了，时间复杂度 O(n*k)。

优先队列 优先队列用来维护窗口内的最大值，如果我们能够总是让窗口内的最大值在队列的头部，那么我们就可以在 O(1) 的时间内获取窗口内的最大值（直接取头部元素）。关键就是如何实现这个维护窗口最大值的操作。

要让第一个是最大值的话，首先想到的是一个递减的队列。我们期待窗口中的所有元素总是从大到小排序，但是对k个元素排序岂不是更浪费时间。关键在于，我们不需要考虑所有元素，我们只关心最大、次大...的元素。

javascript

// nums , k
let Q = [] //mono-Decrease-Queue
for(let i = 0 ; i < nums.length; i++){
  // 但凡当前元素比Q的末尾元素大，我们只关心大元素，直接弹出末尾元素
  while(Q.length > 0 && nums[i] > Q[Q.length - 1]){
    Q.pop()
  }
  // 插入这个大！元素
  Q.push(nums[i])
}

❓上面代码的结果如何呢当序列为[1,6,3], 最终Q会是[6,3] 当序列为[3,2,4,5,1], 最终Q会是[5,1]

类似的，在窗口每滑动一步，我们都要做这几件事：

考虑移出窗口的头部如果这个头恰好等于最大值，他无了，那我们的单调队列也得把头弹出，要维持队列内数据的准确性
考虑移入窗口尾部的新元素弹出队尾：如果当前元素比队尾对应的元素大，那就把队尾弹出（要保持单调性！），到合适的位置插入当前元素

这样子，在每一步滑动的过程中，Q总是存储了窗口中的最大值，且是一个递减的序列，取头即可。

🌟 347. 前k个高频元素

topk问题：类似的还有求前k个最大的数，通常是两种解决方案，一个是利用小顶堆，一个是利用快速排序的兄弟Quick-Selction,堆的内容再专门写一下。这里先讲一下快速选择的思路。

function qSelect(arr, left, right, k) {

    if (left >= right) return

    const m = (left + right) / 2 | 0
    swap(arr, m, left)

    let i = left, j = right
    const pivot = arr[i]

    while (i < j) {

        // 降序
        while (i < j && arr[j] < pivot) j--
        if (i < j) {
            // 找到一个大于等于pivot的数，填到左边
            arr[i] = arr[j]
            i++
        }
        while (i < j && arr[i] >= pivot) i++
        if (i < j) {
            // 找到一个小于pivot的数，填到右边
            arr[j] = arr[i]
            j--
        }
    }

    // 把pivot填到空位
    arr[i] = pivot

    // if (i < k) {
    //     qSelect(arr, left, i - 1, k)
    //     qSelect(arr, i + 1, right, k)
    // } else {
    //     qSelect(arr, left, i - 1, k)
    // }

    if (i === k) return
    else if (i < k) qSelect(arr, i + 1, right, k)
    else if (i > k) qSelect(arr, left, i - 1, k)
}

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](../assets/394. png)

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)
    }
  }
// 1，6，5，2，3
// 1
// 1 6
// 1 5
// 1 2
// 1 2 3

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

栈和队列 ​

简单说明 ​

232 用栈实现队列 ​

225. 用队列实现栈 ​

20. 有效的括号 ​

150. 逆波兰表达式求值 ​

🌟 239. 滑动窗口最大值 ​

🌟 347. 前k个高频元素 ​

155. 最小栈 ​

227. 基本计算器II ​

232. 用栈实现队列 ​

394. 字符串解码 ​

946. 验证栈序列 ​

单调栈 ​

单调栈适用场景 ​

496. 下一个更大元素I ​

739. 每日温度 ​

503. 下一个更大元素II ​

901. 股票价格跨度 ​

316. 去除重复字母 ​