LeetCode_084: Largest Rectangle in Histogram

        经典的题目,最开始没想到这种解法,只想着用优先队列去解了,看了下答案,大概有两种解法,一种是DP,另一种是维护一个栈,这种解法应该是见过最好的了。惯例,贡献高质量解法。

题目

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

分析

这里主要是维护一个栈,这个栈存储的是数组的小标。并且栈中元素从底向上,高度是依次递增的。

也就是说,再往后面搜索时,高峰会被磨平,栈中记录的,都是高于当前区间有效值的低谷值。如在搜索21时,取决于1,搜索到215时,就自动试做115,第一个1省略了,栈记录最新的低谷。

算法遍历原直方图数组每个bar,如果栈顶元素比当前bar的元素高或相等,那么就一直出栈,并计算元素值。关于算法的理解,参见这篇博客的解释(虽然代码不同,但大致意思相同,我把它摘录在下面)。


For example,
Given height = [2,1,5,6,2,3],
return 10.

首先想到一种最直观的方法:把平面看做大矩阵,条形看做1,非条形看做0,寻找最大全1矩阵。

思路上是正确的,可以用DP来做,不过会超时。

网上看到一种借助栈的做法,代码很漂亮,但是解释都非常模糊,我看懂之后,决定仔细描述思路如下:

1、如果已知height数组是升序的,应该怎么做?

比如1,2,5,7,8

那么就是(1*5) vs. (2*4) vs. (5*3) vs. (7*2) vs. (8*1)

也就是max(height[i]*(size-i))

2、使用栈的目的就是构造这样的升序序列,按照以上方法求解。

但是height本身不一定是升序的,应该怎样构建栈?

比如2,1,5,6,2,3

(1)2进栈。s={2}, result = 0

(2)1比2小,不满足升序条件,因此将2弹出,并记录当前结果为2*1=2。

将2替换为1重新进栈。s={1}, result = 2

(3)5比1大,满足升序条件,进栈。s={1,5},result = 2

(4)6比5大,满足升序条件,进栈。s={1,5,6},result = 2

(5)2比6小,不满足升序条件,因此将6弹出,并记录当前结果为6*1=6。s={1,5},result = 6

2比5小,不满足升序条件,因此将5弹出,并记录当前结果为5*2=10(因为已经弹出的5,6是升序的)。s={1},result = 10

2比1大,将弹出的5,6替换为2重新进栈。s={1,1,2,2,2},result = 10  注:这里s事实上只存储了1,2的下表,可以恢复它们的位置,这里为了方便理解,就写出来直观的意思了。

(6)3比2大,满足升序条件,进栈。s={1,1,2,2,2,3},result = 10

栈构建完成,满足升序条件,因此按照升序处理办法得到上述的max(height[i]*(size-i))=max{3*1, 2*2, 2*3, 2*4, 1*5, 1*6}=8<10

综上所述,result=10


        在代码中,与上面的描述有两点不同,一是栈s存储的是数组下标的索引,二是在直方图末尾增加一个0作为哨兵,方便计算最后一个bar引起的面积(0可以使所有元素出栈,也就是上面第六步中的最后计算)。

代码

class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		int res = 0;
		stack<int> si;
		heights.push_back(0); // NIL
		const int n = heights.size();
		for (int i = 0; i < n; ++i){
			while (!si.empty() && heights[si.top()] >= heights[i]){
				int h = heights[si.top()];
				si.pop();
				int s = h * (si.empty() ? i : (i - si.top() - 1));
				res = max(res, s);
			}
			si.push(i);
		}
		return res;
	}
};

 

 

发表评论