单调栈

ゝ一纸荒年。 2022-05-12 07:28 261阅读 0赞

通过使用栈这个简单的结构，我们可以巧妙地降低一些问题的时间复杂度。

单调栈性质：

1、若是单调递增栈，则从栈顶到栈底的元素是严格递增的。若是单调递减栈，则从栈顶到栈底的元素是严格递减的。

2、越靠近栈顶的元素越后进栈。（显而易见）

本文介绍单调栈用法

通过一道题来说明。

POJ2559

**1. 题目大意：[链接][Link 1]**

给出一个柱形统计图(histogram), 它的每个项目的宽度是1， 高度和具体问题有关。 现在编程求出在这个柱形图中的最大面积的长方形。

7 2 1 4 5 1 3 3

7表示柱形图有7个数据，分别是 2 1 4 5 1 3 3， 对应的柱形图如下，最后求出来的面积最大的图如右图所示。

![format_png][]

做法1：枚举每个起点和终点，矩形面积就是长\*最小高度。O(N^3)

做法2：区间最小值优化。O(N^2)

做法3：以每一个下标为中心向两边扩，遇到更短的就停，这样我们可以确定以每一个下标高度为最高的矩形。O(N^2)

单调栈：维护一个单调递增栈，所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。

过程：

1）判断当前元素小于栈顶

2）条件满足，就可以更新栈顶元素的最大长度了，并且把栈顶弹出

3）继续执行（1），直到条件不满足。

**重要结论：**

**1）栈顶下面一个元素一定是，栈顶左边第一个比栈顶小的元素**

**2）当前元素一定是，右边第一个比栈顶小的元素。**

为什么呢？

比如这是个栈

，![20190904185308989.png][]

1）**如果右边存在距离更近的比1号小的数**，1号早已经弹出了。

2）**如果左边有距离更近的比1号小的数**，

如果它比2号小，它会把2号弹出，自己成为2号

如果它比2号大，它不会弹出2号，但是它会压栈，变成2号，原来的2号成为3号。

所以不管怎么说，这个逻辑是正确的。

最后放代码并讲解

下面看一道难一些的题

LeetCode 85 Maximal Rectangle

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 6.二三行后面那六个1

给定一个由二进制组成的矩阵map，找到仅仅包含1的最大矩形，并返回其面积。

这道题是一行一行的做。对每一行都求出每个元素对应的高度，这个高度就是对应的连续1的长度，然后对每一行都更新一次最大矩形面积。

连续1长度也很好更新，本个元素是0，长度就是0，本个元素是1，那就加上之前的。

具体思路代码中讲解。

import java.util.Stack;
    
    public class MaximalRectangle {
    
    	public static int maxRecSize(int[][] map) {
    		if (map == null || map.length == 0 || map[0].length == 0) {
    			return 0;
    		}
    		int maxArea = 0;
    		int[] height = new int[map[0].length];
    		for (int i = 0; i < map.length; i++) {
    			for (int j = 0; j < map[0].length; j++) {
    				height[j] = map[i][j] == 0 ? 0 : height[j] + 1;//0长度为0，1长度为前面+1
    			}
    			maxArea = Math.max(maxRecFromBottom(height), maxArea);//调用第一题的思想
    		}
    		return maxArea;
    	}
    
    	//第一题思路
    	public static int maxRecFromBottom(int[] height) {
    		if (height == null || height.length == 0) {
    			return 0;
    		}
    		int maxArea = 0;
    		Stack<Integer> stack = new Stack<Integer>();
    		for (int i = 0; i < height.length; i++) {
                    //栈非空并且栈顶大
    			while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
    				int j = stack.pop();//弹出
    				int k = stack.isEmpty() ? -1 : stack.peek();
    				int curArea = (i - k - 1) * height[j];//计算最大
    				maxArea = Math.max(maxArea, curArea);//更新总体最大
    			}
    			stack.push(i);//直到栈顶小，压入新元素
    		}
    		//最后栈非空，右边没有更小元素使它们弹出
    		while (!stack.isEmpty()) {
    			int j = stack.pop();
    			int k = stack.isEmpty() ? -1 : stack.peek();
    			int curArea = (height.length - k - 1) * height[j];
    			maxArea = Math.max(maxArea, curArea);
    		}
    		return maxArea;
    	}
    
    	public static void main(String[] args) {
    		int[][] map = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, };
    		System.out.println(maxRecSize(map));
    	}
    
    }

[Link 1]: http://poj.org/problem?id=2559
[format_png]: /images/20220512/5ccaafd698c74edb818b6f6b698b8246.png
[20190904185308989.png]: /images/20220512/2d434241bf0b4bc98ff396da32a38216.png