代码随想录第六十天

代码随想录第六十天

84.柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

本题使用单调栈方法时需要维持一个从栈顶到栈底递减的单调栈，入栈的元素是数组对应元素的下标，如果当前元素比栈顶元素大，入栈，相等，先将栈顶相等元素弹出，然后再入栈，当当前元素比栈顶元素小，就要计算结果，并弹出元素，直到当前元素可以入栈
代码如下：

int maxRectangle(vector<int>& nums)
	{
		nums.insert(nums.begin(), 0);
		nums.push_back(0);
		stack<int>stackResult;
		stackResult.push(0);
		int result = INT_MIN;
		for (int i=1;i<nums.size();i++)
		{
			if (nums[i]>nums[stackResult.top()])
			{
				stackResult.push(i);
			}
			else if (nums[i]==nums[stackResult.top()])
			{
				while (!stackResult.empty()&&nums[i]==nums[stackResult.top()])
				{
					stackResult.pop();
				}
				stackResult.push(i);
			}
			else
			{
				while (!stackResult.empty()&&nums[i]<nums[stackResult.top()])
				{
					int top = stackResult.top();
					stackResult.pop();
					if (!stackResult.empty())
					{
						int tmp = i - stackResult.top()-1;
						int t = nums[top] * tmp;
						result = max(result, t);
					}
				}
				stackResult.push(i);
			}
		}
		return result;
	}
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
27
28
29
30
31
32
33
34
35
36
37
38
39