本文共 2268 字，大约阅读时间需要 7 分钟。

原题链接：

一：原题内容

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

7 2 1 4 5 1 3 34 1000 1000 1000 10000

84000

二：分析理解

利用stack来做，其实利用了压缩的思想，每个push进栈的值都是相较于前一个进栈的较小值。

三：AC代码

#include
   
      #include
    
     #include
     
      #include
      
         using namespace std;long long int heights[100005];//64位int main(){	int n;	while (scanf("%d", &n) && n)	{		for (int i = 0; i < n; i++)			scanf("%I64d", &heights[i]);//64位		stack
       
         s;		long long int ans = 0;//64位		for (int i = 0; i < n; i++)		{			if (s.empty() || heights[i]>heights[s.top()])				s.push(i);			else			{				int cur = s.top();				s.pop();				long long int width = s.empty() ? i : i - s.top() - 1;				ans = max(ans, width*heights[cur]);				i--;//!!!			}		}		while (!s.empty())		{			int cur = s.top();			s.pop();			long long int width = s.empty() ? n : n - s.top() - 1;			ans = max(ans, width*heights[cur]);		}		printf("%I64d\n", ans);//64位的输出，坑	}	return 0;}
       
      
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/50954873 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！