单调栈进阶-接雨水-最大矩形

1 前言

在前阵子的一篇分享里,简单提到了单调栈这个数据结构,文章如下↓↓↓

分享一个简单但挺有意思的算法题2-贪心-单调栈-动态规划

当时只是用单调栈解决了股票问题,是最基础的入门示例,算是easy或者勉强medium级别,今天用单调栈来解决一些hard题目

2 示例-接雨水

42. 接雨水

这是一道经典的面试题,解法有三种,一是正反遍历求出每个点的左右最大高度,勉强算动态规划;二是单调栈;三是双指针;其中效率最高的是双指针,最低的是正反遍历,单调栈效率和双指针是一样的,只是多使用了一个栈结构,故而空间复杂度不是最优。

2.1 单调栈的思路

不难想到,每一个点能接到的雨水,取决于该点左右两边的最大高度,两者之间的最小值即雨水的最大高度,方法一的正反遍历也是为了求取左右两边的最大高度,优点是直观好理解,缺点是两次遍历,效率较低。

而仔细思考的话,使用单调栈,维护一个递减的单调栈,也能求取该点左右两边的最大高度,只是不是针对每一个点,而是每一个上坡,只要有上坡,就弹出,并计算雨水;

具体思路是:遇到一个小于栈顶的元素,则入栈,遇到一个大于栈顶的元素,且此时栈非空,则弹出栈顶,此时计算宽度为i - 已弹出的栈顶 - 1,高度为min(height[i], 最新栈顶的高度) - 已弹出的栈顶

2.2 代码

var trap = function(height) {
    let stack = [];
    let len   = height.length
    let res   = 0;
    for(let i=0;i < len;i++){
        while(stack.length > 0 && height[i] > height[stack[stack.length - 1]]){
            let top = height[stack.pop()]
            if(stack.length == 0){
                break
            }
            let width_ = i - stack[stack.length - 1] - 1
            let height_= Math.min(height[i], height[stack[stack.length - 1]]) - top
            res += width_*height_
        }
        stack.push(i)
    }
    return res
};

单调栈进阶-接雨水-最大矩形_第1张图片

3 示例-柱状图中的最大矩形

84. 柱状图中最大的矩形

3.1 单调栈的思路

这个跟上一题的思路基本一致,只是这里变成了维护一个单调递增栈,遇到一个大于栈顶的元素就入栈,遇到一个小于栈顶的元素,说明上坡结束,需要一次弹出栈顶,计算最大面积了,此时高度为刚刚弹出的栈顶对应的高度,宽度为i - 最新栈顶下标 - 1(PS:宽度不能是i - 刚刚弹出的栈顶对应的下标,因为heights[i]可能连续小于最新栈顶,此时宽度会连续横向拓宽)

3.2 代码

var largestRectangleArea = function(heights) {
    heights.push(0)
    heights.unshift(0)
    let stack = []
    let len = heights.length
    let res = 0
    for(let i=0;i < len;i++){
        while(stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]){
            //吐出来个
            let top_i  = stack.pop(stack)
            let height = heights[top_i]
            let width  = i - stack[stack.length - 1] - 1
            res = Math.max(res, height*width)
        }
        stack.push(i)
    }
    return res
};

单调栈进阶-接雨水-最大矩形_第2张图片

4 示例-最大矩形

85. 最大矩形

4.1 单调栈思路

这道题基本和柱状图中的最大矩形没有啥区别,柱状图中的最大矩形是计算了一层,这个是计算多层,我们把每一行都当做一个柱状图,求出每一层的最大矩形,其中最大值就是最终答案。

matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
//转化成柱状图后是
heights = [
    [ 1 , 0 , 1 , 0 , 0 ],
    [ 2 , 0 , 2 , 1 , 1 ],
    [ 3 , 1 , 3 , 2 , 2 ],
    [ 4 , 0 , 0 , 3 , 0 ]
]

heights遍历,求取每一行的最大矩形即可

4.2 代码

var largestRectangleArea = function(heights) {
    heights.push(0)
    heights.unshift(0)
    let stack = []
    let len = heights.length
    let res = 0
    for(let i=0;i < len;i++){
        while(stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]){
            //吐出来个
            let top_i  = stack.pop(stack)
            let height = heights[top_i]
            let weight = i - stack[stack.length - 1] - 1
            res = Math.max(res, height*weight)
        }
        stack.push(i)
    }
    return res
};
var maximalRectangle = function(matrix) {
    let h    = matrix.length
    let w    = matrix[0].length
    let tree = [];
    let res  = 0;
    for (let i = 0; i < h; i++) {
        tree[i] = new Array(w)
        for (let j = 0; j < w; j++) {
            //树的高度
            if (matrix[i][j] == '0') {
                tree[i][j] = 0
            }else{
                tree[i][j] = i > 0 ? tree[i-1][j] + 1 : 1
            }
        }
        let this_line = largestRectangleArea(tree[i].concat())//这里因为js的天生短板,要使用深拷贝
        res = Math.max(res, this_line)
    }
    return res
};

单调栈进阶-接雨水-最大矩形_第3张图片

你可能感兴趣的