POJ 2559 Largest Rectangle in a Histogram(单调栈)
【题目链接】:click here~~
【题目大意】:
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.
Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000
建立一个单调递增栈,全部元素各进栈和出栈一次,每次出栈的时候更新一下最大值
代码:
// C #ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif // C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; #define rep(i,j,k) for(int i=j;i<k;++i) #define per(i,j,k) for(int i=(int)j;i>(int)k;--i) #define lowbit(a) a&-a #define Max(a,b) a>b?a:b #define Min(a,b) a>b?b:a #define mem(a,b) memset(a,b,sizeof(a)) typedef long long LL; typedef unsigned long long LLU; typedef double db; const int N=2*1e5+10; int n,m,top; int num[N],W[N],H[N]; char str[N]; bool vis[N]; int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; struct node ///定义栈的结构体,高度:宽度 { int height; int width; }; node Dull_Stack[N]; int main() { LL ans,tot,tmp,Max_area; while(scanf("%d",&n)!=EOF&&n) { ans=0; top=0; rep(i,0,n) { scanf("%d",&m); tmp=0; while(top>0&&Dull_Stack[top-1].height>=m)///(2,1) (1,2)的情况 { tot=Dull_Stack[top-1].height*(Dull_Stack[top-1].width+tmp);///更新宽度 //ans=max(tot,ans); if(tot>ans) ans=tot; tmp+=Dull_Stack[top-1].width; --top; /* printf("Dull_Stack[top-1].height= %lld\n",Dull_Stack[top-1].height); printf("Dull_Stack[top-1].width= %lld\n",Dull_Stack[top-1].width); printf("ans= %lld\n",ans); printf("tot= %lld\n",tot); */ } Dull_Stack[top].height=m;///继续输入 Dull_Stack[top].width=tmp+1; ++top; } /* printf("tot=%lld\n",tot); printf("ans=%lld\n",ans); */ tmp=0; while(top>0) { Max_area=Dull_Stack[top-1].height*(Dull_Stack[top-1].width+tmp); //ans=max(Max_area,ans); if(Max_area>ans) ans=Max_area; tmp+=Dull_Stack[top-1].width; ///printf("%lld\n",Max_area); --top; } printf("%lld\n",ans); } return 0; } /* Sample Input 7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0 Sample Output 8 4000 */
相关文章
- 快速搭建Fabric测试网络(Docker in Ubantu 18.04 TLS)
- 故障分析 | 报错 ERROR 5270 -HY000-- object not in RECYCLE BIN 引发的几个思考
- ORA-01239: database must be in ARCHIVELOG mode to use external cache ORACLE 报错 故障修复 远程处理
- ORA-24400: error occured while creating connections in the pool ORACLE 报错 故障修复 远程处理
- ORA-29849: error occurred in the execution of ODCIINDEXSPLITPARTITION routine ORACLE 报错 故障修复 远程处理
- ORA-01097: cannot shutdown while in a transaction – commit or rollback first ORACLE 报错 故障修复 远程处理
- ORA-01249: archiving not allowed in a clone database ORACLE 报错 故障修复 远程处理
- ORA-08002: sequence string.CURRVAL is not yet defined in this session ORACLE 报错 故障修复 远程处理
- ORA-14283: UNIQUE constraints mismatch in ALTER TABLE EXCHANGE SUBPARTITION ORACLE 报错 故障修复 远程处理
- PostgreSQL 55006: object_in_use 报错 故障修复 远程处理
- in Neo4j查询:使用Not In操作(neo4j查询not)
- 查询Oracle中执行多列IN查询的技巧(oracle多列in)
- MySQL排序技巧:使用IN指令(mysql根据in排序)
- MySQL中使用IN子查询的技巧(mysql子查询in)
- Effortlessly Modify Values in Oracle: A Comprehensive Guide(oracle修改值)
- Exploring the Power of Max Function in Oracle: A Comprehensive Guide(max函数oracle)
- 语句SQL Server中使用IN语句处理多值查询(sqlserver中in)
- MySQL中利用IN查询实现多参数搜索(mysql的in查询)
- MySQL的IN操作符对于查询中给定的值列表长度是有限制的(mysql中in长度限制)
- MySQL中IN操作的高效优化(mysql 中in的优化)
- MySQL中IN操作存在漏洞(mysql中in有漏)
- 如何优化MySQL中的IN查询语句(mysql中in怎么优化)
- 深入剖析MySQL中IN和等于操作的差异与应用(mysql中in和等于)
- 以Oracle IN查询精准定位你要的信息(oracle使用in查询)
- MySQL不支持IN运算符如何解决(mysql 不支持in)
- 语法 在Oracle中使用IN子句实现查询(oracle中支持in)
- 操作Oracle中掌握字符串IN操作的技巧(oracle中字符串in)
- 符号Oracle 中与 IN 的区别(Oracle中=和in)
- 限制解除Oracle中IN语句数量限制(oracle中in的数量)
- Oracle中两个IN叠加的查询技巧(oracle两个in叠加)