大厂算法面试之leetcode精讲13.枯燥栈
视频解说（高效学习）:点击学习
目录：
1.开篇介绍
2.工夫空间复杂度
3.动静布局
4.贪婪
5.二分查找
6.深度优先&广度优先
7.双指针
8.滑动窗口
9.位运算
10.递归&分治
11剪枝&回溯
12.堆
13.枯燥栈
14.排序算法
15.链表
16.set&map
17.栈
18.队列
19.数组
20.字符串
21.树
22.字典树
23.并查集
24.其余类型题
239. 滑动窗口最大值 (hard)
办法1.优先队列
动画过大，点击查看
- 思路：最大值问题咱们能够采纳大顶堆，具体就是保护一个大顶堆，初始的时候将
0～k-1的元素退出堆中，存入的是值和索引的键值队，而后滑动窗口从从索引为k的元素开始遍历，将新进入滑动窗口的元素加堆中，当堆顶元素不在滑动窗口中的时候，一直删除堆顶堆元素，直到最大值在滑动窗口里。 - 复杂度剖析：工夫复杂度
O(nlogn)，n是nums的长度，将一个元素退出优先队列的工夫复杂度是logn，最坏的状况下所有元素都要入队，所以复杂度是nlogn。空间复杂度是O(n)，最坏的状况下，所有元素都在队列中，所以是O(n)
js:
class Heap { constructor(comparator = (a, b) => a - b, data = []) { this.data = data; this.comparator = comparator;//比拟器 this.heapify();//堆化 } heapify() { if (this.size() < 2) return; for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) { this.bubbleDown(i);//bubbleDown操作 } } peek() { if (this.size() === 0) return null; return this.data[0];//查看堆顶 } offer(value) { this.data.push(value);//退出数组 this.bubbleUp(this.size() - 1);//调整退出的元素在小顶堆中的地位 } poll() { if (this.size() === 0) { return null; } const result = this.data[0]; const last = this.data.pop(); if (this.size() !== 0) { this.data[0] = last;//替换第一个元素和最初一个元素 this.bubbleDown(0);//bubbleDown操作 } return result; } bubbleUp(index) { while (index > 0) { const parentIndex = (index - 1) >> 1;//父节点的地位 //如果以后元素比父节点的元素小，就替换以后节点和父节点的地位 if (this.comparator(this.data[index], this.data[parentIndex]) < 0) { this.swap(index, parentIndex);//替换本人和父节点的地位 index = parentIndex;//一直向上取父节点进行比拟 } else { break;//如果以后元素比父节点的元素大，不须要解决 } } } bubbleDown(index) { const lastIndex = this.size() - 1;//最初一个节点的地位 while (true) { const leftIndex = index * 2 + 1;//左节点的地位 const rightIndex = index * 2 + 2;//右节点的地位 let findIndex = index;//bubbleDown节点的地位 //找出左右节点中value小的节点 if ( leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 ) { findIndex = leftIndex; } if ( rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 ) { findIndex = rightIndex; } if (index !== findIndex) { this.swap(index, findIndex);//替换以后元素和左右节点中value小的 index = findIndex; } else { break; } } } swap(index1, index2) {//替换堆中两个元素的地位 [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]]; } size() { return this.data.length; }}var maxSlidingWindow = function(nums, k) { let ans = []; let heap = new Heap((a, b) => b.val - a.val);//大顶堆 for(let i=0;i<k-1;i++) heap.offer({val: nums[i], index: i});//初始的时候将0～k-1的元素退出堆中 for(let i=k-1; i<nums.length; i++){//滑动窗口从从索引为k-1的元素开始遍历 heap.offer({val: nums[i], index: i});//将新进入滑动窗口的元素加堆中 //当堆顶元素不在滑动窗口中的时候，一直删除堆顶堆元素，直到最大值在滑动窗口里。 while(heap.peek().index<=i-k) heap.poll(); ans.push(heap.peek().val);//将在滑动窗口里的最大值退出ans } return ans;}java:
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {//大顶堆 public int compare(int[] pair1, int[] pair2) { return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]; } }); for (int i = 0; i < k; ++i) {//初始的时候将0～k-1的元素退出堆中 pq.offer(new int[]{nums[i], i}); } int[] ans = new int[n - k + 1]; ans[0] = pq.peek()[0];//滑动窗口初始最大值 for (int i = k; i < n; ++i) {//滑动窗口从从索引为k的元素开始遍历 pq.offer(new int[]{nums[i], i});//将新进入滑动窗口的元素加堆中 //当堆顶元素不在滑动窗口中的时候，一直删除堆顶堆元素，直到最大值在滑动窗口里。 while (pq.peek()[1] <= i - k) { pq.poll(); } ans[i - k + 1] = pq.peek()[0];//将在滑动窗口里的最大值退出ans } return ans; }}办法2.枯燥队列
动画过大，点击查看
- 思路：保护枯燥递加队列，当进入滑动窗口的元素大于等于队尾的元素时 一直从队尾出队，直到进入滑动窗口的元素小于队尾的元素，才能够入队，以保障枯燥递加的性质，当队头元素曾经在滑动窗口外了，移除对头元素，当i大于等于k-1的时候，枯燥递加队头就是滑动窗口的最大值
- 复杂度剖析：工夫复杂度
O(n)，n是nums的长度，每个元素入队一次。空间复杂度O(k)，队列最多寄存k大小的元素
js:
var maxSlidingWindow = function (nums, k) { const q = [];//单递加的双端队列 const ans = [];//最初的返回后果 for (let i = 0; i < nums.length; i++) {//循环nums //当进入滑动窗口的元素大于等于队尾的元素时 一直从队尾出队， //直到进入滑动窗口的元素小于队尾的元素，以保障枯燥递加的性质 while (q.length && nums[i] >= nums[q[q.length - 1]]) { q.pop(); } q.push(i);//元素的索引入队 while (q[0] <= i - k) {//队头元素曾经在滑动窗口外了，移除对头元素 q.shift(); } //当i大于等于k-1的时候，枯燥递加队头就是滑动窗口的最大值 if (i >= k - 1) ans.push(nums[q[0]]); } return ans;};Java:
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; Deque<Integer> deque = new LinkedList<Integer>(); for (int i = 0; i < k; ++i) { while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } deque.offerLast(i); } int[] ans = new int[n - k + 1]; ans[0] = nums[deque.peekFirst()]; for (int i = k; i < n; ++i) { while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } deque.offerLast(i); while (deque.peekFirst() <= i - k) { deque.pollFirst(); } ans[i - k + 1] = nums[deque.peekFirst()]; } return ans; }}84. 柱状图中最大的矩形 (hard)
- 思路：筹备枯燥递增栈寄存数组下标，因为这样能够从栈顶找到右边第一个比本人小的下标，这样从以后下标登程到第一个比本人小的柱子的下标就是矩形面积的宽度，而后在乘以后柱子的高度就是面积，如果以后柱子大于栈顶的下标对应的柱子高度，就入栈，否则一直出栈，计算栈顶的柱子所能造成的矩形面积，而后更新最大矩形面积
- 复杂度：工夫复杂度
O(n)，n是heights的长度，数组里每个元素尽出栈一次。空间复杂度O(n)，栈空间最多为n
动画过大，点击查看
js：
const largestRectangleArea = (heights) => { let maxArea = 0 const stack = [] //枯燥递增栈 留神栈存的时下标 heights = [0, ...heights, 0] //在heights数组前后减少两个哨兵 用来清零枯燥递增栈里的元素 for (let i = 0; i < heights.length; i++) { //以后元素对应的高度小于栈顶元素对应的高度时 while (heights[i] < heights[stack[stack.length - 1]]) { const stackTopIndex = stack.pop() //出栈 maxArea = Math.max( //计算面积 并更新最大面积 maxArea, heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)//高乘宽 ) } stack.push(i)//以后下标退出栈 } return maxArea}java：
class Solution { public int largestRectangleArea(int[] heights) { Stack<Integer> stack = new Stack<>(); int len = heights.length; int maxArea = 0; for(int i = 0; i < len; i++){ if(stack.isEmpty() || heights[stack.peek()] <= heights[i]) stack.push(i); else{ int top = -1; while(!stack.isEmpty() && heights[stack.peek()] > heights[i]) { top = stack.pop(); maxArea = Math.max(maxArea, heights[top] * (i - top)); } heights[top] = heights[i]; stack.push(top); } } while(!stack.isEmpty()) { int top = stack.pop(); maxArea = Math.max(maxArea, (len - top) * heights[top]); } return maxArea; }}85. 最大矩形 (hard)
办法1.枯燥栈
- 思路：84题的变种，从第一行到第n行造成的柱状图能够利用84题求解，而后循环每一行，计算以这一行为底的柱状图最大面积，而后更新最大矩形面积
- 复杂度：工夫复杂度
O(mn)，m、n别离是矩形的高度和宽度，循环m次行，每行里循环每个柱子的高度。空间复杂度O(n)，heights数组的空间。
js：
var maximalRectangle = function (matrix) { if (matrix.length == 0) return 0; let res = 0; let heights = new Array(matrix[0].length).fill(0);//初始化heights数组 for (let row = 0; row < matrix.length; row++) { for (let col = 0; col < matrix[0].length; col++) { if(matrix[row][col] == '1' ) heights[col] += 1; else heights[col] = 0; }//求出每一层的 heights[] 而后传给84题的函数 res = Math.max(res, largestRectangleArea(heights));//更新一下最大矩形面积 } return res;};const largestRectangleArea = (heights) => { let maxArea = 0 const stack = [] //枯燥递增栈 留神栈存的时下标 heights = [0, ...heights, 0] //在heights数组前后减少两个哨兵 用来清零枯燥递增栈里的元素 for (let i = 0; i < heights.length; i++) { //以后元素对应的高度小于栈顶元素对应的高度时 while (heights[i] < heights[stack[stack.length - 1]]) { const stackTopIndex = stack.pop() //出栈 maxArea = Math.max( //计算面积 并更新最大面积 maxArea, heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)//高乘宽 ) } stack.push(i)//以后下标退出栈 } return maxArea}java：
class Solution { public int maximalRectangle(char[][] matrix) { int row = matrix.length; if (row == 0) return 0; int col = matrix[0].length; int[] heights = new int[col + 1]; heights[col] = -1; int res = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { heights[j] = matrix[i][j] == '1' ? heights[j] + matrix[i][j] - '0' : 0; } res = Math.max(res, largestRectangleArea(Arrays.copyOf(heights, col + 1))); } return res; } public int largestRectangleArea(int[] heights) { Stack<Integer> stack = new Stack<>(); int len = heights.length; int maxArea = 0; for (int i = 0; i < len; i++) { if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) stack.push(i); else { int top = -1; while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) { top = stack.pop(); maxArea = Math.max(maxArea, heights[top] * (i - top)); } heights[top] = heights[i]; stack.push(top); } } return maxArea; }}496. 下一个更大元素 I (easy）
动画过大，点击查看
思路：
- 循环nums2，如果循环的元素大于栈顶元素，并且栈不为空，则一直将栈顶元素作为key，以后元素作为value退出map中
- 实质是第一个比栈顶元素大的值会让栈中的元素一直出队 所以这个数就是这些出栈元素的下一个更大的数
- 剩下来的元素就是没有找到最大值的
- 遍历nums1将后果推入ans中
- 复杂度：工夫复杂度
O(m+n)，nums1、nums2遍历一遍，nums2中的元素入队出队一次。空间复杂度O(n)，栈空间和map的空间的复杂度
js：
let nextGreaterElement = function(nums1, nums2) { let map = new Map(), stack = [], ans = []; //循环nums2，如果循环的元素大于栈顶元素，并且栈不为空，则一直将栈顶元素作为key，以后元素作为value退出map中 //实质是第一个比栈顶元素大的值会让栈中的元素一直出队 所以这个数就是这些出栈元素的下一个更大的数 nums2.forEach(item => { while(stack.length && item > stack[stack.length-1]){ map.set(stack.pop(), item) }; stack.push(item); }); stack.forEach(item => map.set(item, -1));//剩下来的元素就是没有找到最大值的 nums1.forEach(item => ans.push(map.get(item)));//遍历nums1将后果推入ans中 return ans;};java：
public class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int len1 = nums1.length; int len2 = nums2.length; Deque<Integer> stack = new ArrayDeque<>(); Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < len2; i++) { while (!stack.isEmpty() && stack.peekLast() < nums2[i]) { map.put(stack.removeLast(), nums2[i]); } stack.addLast(nums2[i]); } int[] ans = new int[len1]; for (int i = 0; i < len1; i++) { ans[i] = map.getOrDefault(nums1[i], -1); } return ans; }}42. 接雨水 （hard）
思路：首先思考暴力做法，找找思路，暴力做法能够遍历数组，在每个地位别离往两边寻找左柱子中的最大高度和右柱子中的最大高度，找到之后，用左右最大高度的较小者减去以后柱子的高度，就是以后地位能接的水量。该办法要循环整个数组，并且每个地位要遍历数组寻找左右柱子高度的最大值，嵌套了一层循环，所以复杂度是
O(n^2)。咱们怎么减速嵌套的这层循环呢，其实能够事后计算从左往右和从右往左的最大高度数组，在循环数组的时候，能够间接拿到该地位左右两边的最大高度，以后地位的接水量就是左右两边高度的较小者减去以后地位柱子的高度
- 复杂度：工夫复杂度
O(n)，寻找左右的最大高度，循环计算每个地位的接水量，总共3个循环，但他们不是嵌套关系。空间复杂度是O(n)，n是heights数组，用到了leftMax和rightMax数组，即寄存左右两边最大高度的数组。
办法1.动静布局
动画过大，点击查看
js：
var trap = function(height) { const n = height.length; if (n == 0) {//极其状况 return 0; } const leftMax = new Array(n).fill(0);//初始化从左往右看的最大值数组 leftMax[0] = height[0]; for (let i = 1; i < n; ++i) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } const rightMax = new Array(n).fill(0);//初始化从右往左看的最大值数组 rightMax[n - 1] = height[n - 1]; for (let i = n - 2; i >= 0; --i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } let ans = 0; //循环数组，每个地位能接的雨水量就是这个地位左右最大值的较小者减去以后的高度 for (let i = 0; i < n; ++i) { ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans;};java：
class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) { return 0; } int[] leftMax = new int[n]; leftMax[0] = height[0]; for (int i = 1; i < n; ++i) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } int[] rightMax = new int[n]; rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; --i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } int ans = 0; for (int i = 0; i < n; ++i) { ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; }}办法2:枯燥栈
动画过大，点击查看
- 思路：遍历
heights数组，将其中的元素退出枯燥递加栈，如果以后柱子的高度大于栈顶柱子的高度， 一直出栈，相当于找到右边比以后柱子矮的地位，而后每次出栈之后都要累加一下面积。 - 复杂度：工夫复杂度
O(n)，n是heights的长度，数组中的每个元素最多入栈出栈一次。空间复杂度O(n)，栈的空间，最多不会超过heights的长度
js：
var trap = function(height) { let ans = 0; const stack = [];//枯燥递加栈。寄存的是下标哦 const n = height.length; for (let i = 0; i < n; ++i) {//循环heights //以后柱子的高度大于栈顶柱子的 一直出栈 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];//计算高度 ans += currWidth * currHeight;//计算当面积 } stack.push(i);//退出栈 } return ans;};java：
class Solution { public int trap(int[] height) { int ans = 0; Deque<Integer> stack = new LinkedList<Integer>(); int n = height.length; for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) { break; } int left = stack.peek(); int currWidth = i - left - 1; int currHeight = Math.min(height[left], height[i]) - height[top]; ans += currWidth * currHeight; } stack.push(i); } return ans; }}办法3.双指针
动画过大，点击查看
- 思路：如果左边存在一个比以后高的柱子，就会造成一个高地，同理，右边存在一个比以后高柱子，也会造成一个坑，用双指针循环
heights数组，判断是否造成高地，如果能造成高地，则计算积水量，累加进ans。 - 复杂度：工夫复杂度
O(n)，n为heights的长度， 总共遍历heights一次。空间复杂度O(1)，只用到了两个指针
js：
var trap = function(height) { let ans = 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 (height[left] < height[right]) {//左边的柱子高于右边的柱子 计算这个地位的接水量 累加进后果 ans += leftMax - height[left]; ++left; } else { //右边的柱子高于或等于左边的柱子 计算这个地位的接水量 累加进后果 ans += rightMax - height[right]; --right; } } return ans;};java：
class Solution { public int trap(int[] height) { int ans = 0; int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0; while (left < right) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); if (height[left] < height[right]) { ans += leftMax - height[left]; ++left; } else { ans += rightMax - height[right]; --right; } } return ans; }}