单调栈-柱状图中的最大矩形

在这里插入图片描述

代码求解

对于直方图中的每个高度，找到其左右两侧离它最近且比它小的高度位置，以该高度为高向左右两侧拓展，计算拓展的单位数，再乘以该高度得到长方形面积，对每个高度进行遍历，求得最大值。

虽然高度相等的时候弹出的计算结果可能是错误的，但总是会有最后一个相同高度能够算对，所以并不会影响最终求解的最大长方形的面积。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    	public static int MAXN = 100001;
	public static int[] stack = new int[MAXN];
	public static int r;

	public static int largestRectangleArea(int[] height){
		int n = height.length;
		r = 0;
		int ans = 0,cur,left;
		for(int i = 0;i<n;i++){
			while(r>0&&height[stack[r-1]]>=height[i]){
				cur = stack[--r];
				left = r==0?-1:stack[r-1];
				ans = Math.max(ans, height[cur]*(i-left-1));
			}
			stack[r++]=i;
		}

		while (r>0) {
			cur = stack[--r];
			left = r==0?-1:stack[r-1];
			ans = Math.max(ans, height[cur]*(n-left-1));
		}
		return ans;
	}
}