网站建设的运作原理盘古搜索

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;
}

方法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;
};

84. 柱状图中最大的矩形 (hard)

const largestRectangleArea = (heights) => {let maxArea = 0const 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
}

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 = 0const 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
}

496. 下一个更大元素 I (easy）

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;
};

42. 接雨水 （hard）

方法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;
};

方法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;
};

方法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;
};

视频讲解：传送门