Joyce' Blog
0%

largest-rectangle-in-histogram

发表于 更新于

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

题解

其实就是两个柱子之间的事情吧。进行组合选出最大值。

哈哈哈一次过！虽然时空效率不是很好，但至少证明抓住本质 困难题目也会变成简单题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int largestRectangleArea(vector<int>& heights) {
	int vsize = heights.size();
	if (!vsize)return 0;
	int res = heights[0];
	for (int i = 0; i < vsize; i++)
	{
		if (i&&heights[i - 1] >= heights[i])
			continue;
		int low = heights[i];
		for (int j = i; j < vsize; j++)
		{
			low = heights[j] < low ? heights[j] : low;
			int area = (j - i + 1)*low;
			res = area > res ? area : res;
		}
	}
	return res;
}

看了官方解析，觉得自己数据结构还是没学好。

单调递增栈操作规则

  1. 如果新的元素比栈顶元素大，就入栈
  2. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

思路

  1. 对于一个高度，如果能得到向左和向右的边界
  2. 那么就能对每个高度求一次面积
  3. 遍历所有高度，即可得出最大面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int largestRectangleArea(vector<int>& heights)
{
	int ans = 0;
	vector<int> st;
	heights.insert(heights.begin(), 0);
	heights.push_back(0);
	for (int i = 0; i < heights.size(); i++)
	{
		while (!st.empty() && heights[st.back()] > heights[i])
		{
			int cur = st.back();
			st.pop_back();
			ans = max(ans, (i-1 - st.back()) * heights[cur]);
		}
		st.push_back(i);
	}
	return ans;
}