栈和队列
Date:
栈、队列经典题
简单说明
对于js中的Array 栈
- push() 进栈
- pop() 出栈 队列
- push() 进队列
- shift() 出队列
232 用栈实现队列
🖐️ 无需多言， 两个栈实现
- 使用两个栈来实现队列的功能。
- 栈1用于入队，栈2用于出队。
- 当需要出队时，如果栈2为空，则将栈1中的元素全部弹出并压入栈2。
- 然后从栈2中弹出元素作为出队结果。
225.用队列实现栈
- 思路1 - 用两个队列
- 队列1用于入栈，队列2用于出栈。
- 当需要出栈时，如果队列1中只有一个元素，则直接弹出该元素作为出栈结果。
- 如果队列1中有多个元素，则将队列1中的所有元素依次出队并入队到队列2中，直到队列1只剩下一个元素。
- 然后将队列1中的最后一个元素弹出作为出栈结果。
- 思路2 - 一个队列
- 当需要出栈时，将队列中的n-1个元素出队并入队到自身，直到队列中只剩下一个元素。
- 然后弹出最后一个元素作为出栈结果。
20.有效的括号
🖐️ 无需多言, 栈 遇左括push右括号，遇右括号pop匹配
150.逆波兰表达式求值
🖐️ 无需多言, 栈 遇到操作符时，pop b, pop a，然后 oprate(a, b) 注意：
- 先b后a
- 除法的分母
除法的靠0取整， 用 0
🌟 239.滑动窗口最大值
这个就比较吊了，用到了优先队列。
一开始在做这题的时候，总是很难受，想着用一个队列作为窗口，滑动的时候无非就是头部出队尾巴入队，但是如果你想记录窗口内的最大值，你不知道这个最大值是否是第一个元素，或者是中间和末尾的元素，这就导致更新窗口之后，需要再遍历窗口求MAX，这样就超时了，时间复杂度 O(n*k)。
优先队列
优先队列用来维护窗口内的最大值， 如果我们能够总是让窗口内的最大值在队列的头部，那么我们就可以在 O(1) 的时间内获取窗口内的最大值（直接取头部元素）。 关键就是如何实现这个维护窗口最大值的操作。
要让第一个是最大值的话，首先想到的是一个递减的队列。 我们期待窗口中的所有元素总是从大到小排序，但是对k个元素排序岂不是更浪费时间。 关键在于，我们不需要考虑所有元素，我们只关心最大、次大…的元素。
// 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)
}