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

## 2 示例-接雨水

42. 接雨水

### 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.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
};``````