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