栈、队列

栈(Stack),先进后出。Fast In - Last Out、FILO。添加、删除都是 O(1)、查询为 O(n),元素是无序的。

队列(Queue),先进先出。Fast In - First Out、FIFO。 添加、删除都是 O(1)、查询为 O(n),元素是无序的。

双端队列(Deque、Double-End Queue),queue 和 stack 的结合体。插入和删除都是 O(1) 操作。

Java 的 Stack 源码

Java 的 Queue 源码

Python 的 heapq

高性能的 container 库

优先队列(Priority Queue)。
插入操作 O(1),取出操作 O(log n),可以按照元素的优先级取出。
底层具体实现的数据结构较为多样和复杂,可以由 heap、bst、avl 等实现。

Java 的 PriorityQueue 文档

structure_operations.png

https://www.bigocheatsheet.com/

有效的括号(亚马逊、JPMorgan 在半年内面试常考)
最小栈(亚马逊在半年内面试常考)
柱状图中最大的矩形(亚马逊、微软、字节跳动在半年内面试中考过)
滑动窗口最大值(亚马逊在半年内面试常考)

设计循环双端队列(Facebook 在 1 年内面试中考过)
接雨水(亚马逊、字节跳动、高盛集团、Facebook 在半年内面试常考)

// 有效的括号 // 如果一个题目具有最近相关性,它就可以用栈来解决。 // 思路1:暴力求解,不断 replace 匹配括号,O(n^2) // 思路2:Stack /** * @param {string} s * @return {boolean} */ var isValid = function(s) { if (s.length % 2 === 1) return false; const map = new Map([ ['{', '}'], ['[', ']'], ['(', ')'] ]); const stack = []; let c; for (let i = 0; i < s.length; i++) { c = s[i]; if (map.get(c)) { stack.push(map.get(c)); } else { if (stack.pop() !== c) { return false; } } } return stack.length === 0; };
// 最小栈 // 思路:使用辅助栈 // 后续如果遇到用栈来实现队列,都可以考虑使用两个栈来解决 var MinStack = function() { this.stack = []; this.minStack = [Infinity]; }; /** * @param {number} val * @return {void} */ MinStack.prototype.push = function(val) { this.stack.push(val); this.minStack.push( Math.min(this.minStack[this.minStack.length - 1], val) ); }; /** * @return {void} */ MinStack.prototype.pop = function() { this.stack.pop(); this.minStack.pop(); }; /** * @return {number} */ MinStack.prototype.top = function() { return this.stack[this.stack.length - 1]; }; /** * @return {number} */ MinStack.prototype.getMin = function() { return this.minStack[this.minStack.length - 1] };
// 柱状图中最大的矩形(★★★) // 思路1:暴力求解 O(n^3) // 思路2:暴力求解,枚举柱子高度,寻找左右边界 // 思路3:stack,单调递增栈 /** * @param {number[]} heights * @return {number} */ var largestRectangleArea = function(heights) { let maxArea = 0; const stack = []; heights = [0, ...heights, 0]; for (let i = 0; i < heights.length; i++) { while (heights[i] < heights[stack[stack.length - 1]]) { maxArea = Math.max( maxArea, heights[stack.pop()] * (i - stack[stack.length - 1] - 1) ); } stack.push(i); } return maxArea; };
// 滑动窗口最大值(★★★) // 所有的滑动窗口的题目,都可以考虑使用队列解决 // 思路1:暴力求解 O(n*k) // 思路2:单调队列 O(n+k) -> O(n) /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { const queue = [], result = []; for (let i = 0; i < nums.length; i++) { while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) { queue.pop(); } queue.push(i); while (queue[0] <= i - k) { queue.shift(); } if (i >= k - 1) result.push(nums[queue[0]]); } return result; };
// 设计循环双端队列(★★☆) // 思路:数组实现双端队列,数组其实就是一个双端队列,只不过不存在限制 /** * @param {number} k */ var MyCircularDeque = function(k) { this.queue = []; this.maxSize = k; }; MyCircularDeque.prototype.size = function () { return this.queue.length; } /** * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertFront = function(value) { if (this.size() < this.maxSize) { this.queue.unshift(value); return true; } return false; }; /** * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertLast = function(value) { if (this.size() < this.maxSize) { this.queue.push(value); return true; } return false; }; /** * @return {boolean} */ MyCircularDeque.prototype.deleteFront = function() { if (this.size()) { this.queue.shift(); return true; } return false; }; /** * @return {boolean} */ MyCircularDeque.prototype.deleteLast = function() { if (this.size()) { this.queue.pop(); return true; } return false; }; /** * @return {number} */ MyCircularDeque.prototype.getFront = function() { if (this.size()) { return this.queue[0]; } return -1; }; /** * @return {number} */ MyCircularDeque.prototype.getRear = function() { if (this.size()) { return this.queue[this.size() - 1]; } return -1; }; /** * @return {boolean} */ MyCircularDeque.prototype.isEmpty = function() { return this.size() == 0; }; /** * @return {boolean} */ MyCircularDeque.prototype.isFull = function() { return this.size() === this.maxSize; };
// 接雨水(★★★) // 思路1:单调栈 // 思路2:双指针解法 /** * @param {number[]} height * @return {number} */ var trap = function(height) { const stack = []; let maxArea = 0; for (let i = 0; i < height.length; i++) { while (stack.length && height[i] > height[stack[stack.length - 1]]) { const top = stack.pop(); if (!stack.length) break; const left = stack[stack.length - 1]; const currWidth = i - left - 1; const currHeight = Math.min(height[left], height[i]) - height[top]; maxArea += currWidth * currHeight; } stack.push(i); } return maxArea; }; /** * @param {number[]} height * @return {number} */ var trap = function(height) { let maxArea = 0; let left = 0, right = height.length - 1; let leftMax = 0, rightMax = 0; while (left < right) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); if (leftMax < rightMax) { maxArea += leftMax - height[left++]; } else { maxArea += rightMax - height[right--]; } } return maxArea; };