1 前言
在前阵子的一篇分享里，简单提到了单调栈这个数据结构，文章如下↓↓↓
当时只是用单调栈解决了股票问题，是最基础的入门示例，算是easy或者勉强medium级别,今天用单调栈来解决一些hard题目
2 示例-接雨水
这是一道经典的面试题，解法有三种，一是正反遍历求出每个点的左右最大高度，勉强算动态规划；二是单调栈；三是双指针；其中效率最高的是双指针，最低的是正反遍历，单调栈效率和双指针是一样的，只是多使用了一个栈结构，故而空间复杂度不是最优。
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 示例-柱状图中的最大矩形
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 示例-最大矩形
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
};
