用javascript分类刷leetcode13.单调栈(图文视频讲解)_2023-02-28

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
}

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

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

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

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

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

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

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
}