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

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