乐趣区

关于算法:单调栈进阶接雨水最大矩形

jiezi

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

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

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

退出移动版