最大矩形面积——单调栈问题描述问题分析代码实现

69 阅读 0 评论 46 点赞

我是靠谱客的博主魁梧招牌，最近开发中收集的这篇文章主要介绍最大矩形面积——单调栈问题描述问题分析代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述

给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。
在这里插入图片描述
Input
输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 <= n <= 100000. 然后接下来n个整数h1, …, hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。测试数据以0结尾。
Output
对于每组测试数据输出一行一个整数表示答案。
Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000

问题分析

单调栈

单调栈 = 栈内元素 自栈顶到栈底 满足 单调性
模拟单调递增栈的操作
现有一数组 [10, 3, 7, 4, 12]，从左到右依次入栈。
如果栈为空或者栈顶元素大于入栈元素，则入栈。
否则，入栈则会破坏栈内元素的单调性，则需要将不满足条件的栈顶元素全部弹出后，将入栈元素入栈。
具体过程
10 入栈时, 栈空, 入栈
3 入栈时, 栈顶元素 10 大于 3, 入栈
7入栈时, 栈顶元素 3 小于 7, 弹栈; 栈顶元素 10 大于 7, 入栈
4 入栈时, 栈顶元素 7 大于 4, 入栈
12 入栈时, 栈顶元素 4 小于 12, 弹栈; 栈顶元素 7 小于 12, 弹栈; 栈顶元素 10 小于 12, 弹栈; 栈空, 入栈

解题思路

要找最大矩形面积，即要从当前矩形向左向右分别寻找不小于当前高度的距离。

按照这个思路，如果使用单调栈的话，我们就可以只需要从左至右一遍，然后从由右至左来一遍，分别找出每个点的最右距离和最左距离，只需要遍历两次就可以计算出每个点的最大矩形面积，时间复杂度为O(n)。

因为我们要找出第一个小于当前高度的矩形，因此我们选择维护单调递增栈。从1到n遍历，只有当此时遍历到的点的大小大于单调栈顶时，才能加入到单调栈中；若小于栈顶，则栈顶循环弹出，直到栈顶的大小小于此时的点的高度。对于那些被弹出的点，他们对应的最右元素就是此时遍历到的点。
当倒序遍历时，最左元素是此时遍历到的点。

代码实现

#include<stdio.h>
#include<stack>
#include<math.h>
#define N 100050
using namespace std;
//数据类型long long，否则会WA 
int n =0;
long long int a[N], L[N], R[N];
stack<int> s;

int main()
{
    scanf("%d",&n);
	while( n != 0)
	{
		for(int i=1; i<=n; i++)
		    scanf("%lld",&a[i]);
		
		long long int ans=0;
		R[n] = n;
		L[1] = 1;
		for(int i=1; i<=n; i++)
		{
			while(!s.empty() && a[s.top()] > a[i])
			{// 栈首的下标temp对应的元素大于当前元素，说明temp的最右元素就是当前元素。
				int temp = s.top();
				s.pop();
				R[temp] = i-1;
			}
			s.push(i);
		}
		while(!s.empty()){
			R[s.top()] = n;
			s.pop();
		}
		
		for(int i=n; i>0; i--)
		{
			while(!s.empty() && a[s.top()] > a[i])
			{
				int temp = s.top();
				s.pop();
				L[temp] = i+1;
			}
			s.push(i);
		}
		while(!s.empty()){
			L[s.top()] = 1;
			s.pop();
		}
		
		for(int i=1; i<=n; i++)
		{
			int len = R[i] - L[i] + 1;
			long long int sur = len * a[i];
			if(sur > ans) ans = sur;
		}
		printf("%lldn", ans);
		scanf("%d",&n);
	}
	return 0;
 }