关于leetcode:用javascript分类刷leetcode13单调栈图文视频讲解

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

给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。

求在该柱状图中，可能勾画进去的矩形的最大面积。

示例 1:

输出：heights = [2,1,5,6,2,3]
输入：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：

输出：heights = [2,4]
输入：4

提醒：

1 <= heights.length <=105
0 <= heights[i] <= 104

• 思路：筹备枯燥递增栈寄存数组下标，因为这样能够从栈顶找到右边第一个比本人小的下标，这样从以后下标登程到第一个比本人小的柱子的下标就是矩形面积的宽度，而后在乘以后柱子的高度就是面积，如果以后柱子大于栈顶的下标对应的柱子高度，就入栈，否则一直出栈，计算栈顶的柱子所能造成的矩形面积，而后更新最大矩形面积
• 复杂度：工夫复杂度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
}

85. 最大矩形 (hard)

给定一个仅蕴含 0 和 1、大小为 rows x cols 的二维二进制矩阵，找出只蕴含 1 的最大矩形，并返回其面积。

示例 1：

输出：matrix = [[“1″,”0″,”1″,”0″,”0”],[“1″,”0″,”1″,”1″,”1”],[“1″,”1″,”1″,”1″,”1”],[“1″,”0″,”0″,”1″,”0”]]
输入：6
解释：最大矩形如上图所示。
示例 2：

输出：matrix = []
输入：0
示例 3：

输出：matrix = [[“0”]]
输入：0
示例 4：

输出：matrix = [[“1”]]
输入：1
示例 5：

输出：matrix = [[“0″,”0”]]
输入：0

提醒：

rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrixi 为 ‘0’ 或 ‘1’

办法 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
}

42. 接雨水（hard）

给定 n 个非负整数示意每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输出：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输入：6
解释：下面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 示意的高度图，在这种状况下，能够接 6 个单位的雨水（蓝色局部示意雨水）。
示例 2：

输出：height = [4,2,0,3,2,5]
输入：9

提醒：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

• 思路：首先思考暴力做法，找找思路，暴力做法能够遍历数组，在每个地位别离往两边寻找左柱子中的最大高度和右柱子中的最大高度，找到之后，用左右最大高度的较小者减去以后柱子的高度，就是以后地位能接的水量。该办法要循环整个数组，并且每个地位要遍历数组寻找左右柱子高度的最大值，嵌套了一层循环，所以复杂度是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;
};

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

239. 滑动窗口最大值 (hard)

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右挪动一位。

返回 滑动窗口中的最大值。

示例 1：

输出：nums = [1,3,-1,-3,5,3,6,7], k = 3
输入：[3,3,5,5,6,7]
解释：
滑动窗口的地位 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：

输出：nums = [1], k = 1
输入：[1]

提醒：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

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

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

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应地位 右侧 的 第一个 比 x 大的元素。

给你两个 没有反复元素 的数组 nums1 和 nums2，下标从 0 开始计数，其中 nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length，找出满足 nums1[i] == nums2[j] 的下标 j，并且在 nums2 确定 nums2[j] 的 下一个更大元素。如果不存在下一个更大元素，那么本次查问的答案是 -1。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素。

示例 1：

输出：nums1 = [4,1,2], nums2 = [1,3,4,2].
输入：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

• 4，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1。
• 1，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3。
• 2，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1。
  示例 2：

输出：nums1 = [2,4], nums2 = [1,2,3,4].
输入：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

• 2，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3。
• 4，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1。

提醒：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1 和 nums2 中所有整数 互不雷同
nums1 中的所有整数同样呈现在 nums2 中

进阶：你能够设计一个工夫复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

动画过大，点击查看

• 思路：

  1. 循环 nums2，如果循环的元素大于栈顶元素，并且栈不为空，则一直将栈顶元素作为 key，以后元素作为 value 退出 map 中
  2. 实质是第一个比栈顶元素大的值会让栈中的元素一直出队 所以这个数就是这些出栈元素的下一个更大的数
  3. 剩下来的元素就是没有找到最大值的
  4. 遍历 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;
};

视频解说：传送门