【题目】
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.
【题意】
即一共有个木板，每个木板宽度为1，长度为
。然后找到用这些模板接在一起后，可以用笔划出一个矩形的最大面积。
【题解】
这里一道单调栈的裸题。单调栈是一种数据结构，在最基础的单调栈中，最开头的数即是最大值（或者最小值），整个数据结构的序列成单调递减（或者单调递增），而更新序列中的数值是采取栈的先进后出的栈的形式，所以称为这种数据结构为单调栈。
单调栈在项目中的作用倒是比较少见，不过在ACM/ICPC中的使用，则是挺多见的，所以学会这个数据结构是打算法竞赛必经之路。所以在学习的过程中，个人并不建议深究其具体的作用，而先掌握使用方法，找到其的特性后，结合题目，写出最终的解法。
在这道题中，看完题目后，可以发现长的木板会被短的木板给截断，即无法再往短的木板上画相对较长木板的矩形。那么我们只需要在单调栈中维护含有最小值和木板宽度的结构体
,
即可，即循环输入的数，当单调栈中没有值时，添加当前
和当前宽度
（当前没有比这个数再短的木板）的值。而当单调栈有值时，并且当前
小于单调栈最上面的那个数，就把单调栈最上面的数取出，
即为当前取出木板的最长延伸宽度，并且当前值的
继承长木板的宽度，因为按照当前的短木板的长度，可以继续往被取出的宽度画过去。循环结束后，整个单调栈中的值，成一个单调递减的事态，这样也就是说当前单调栈中最后一个数的最长的木板的宽度，已经无法往小的木板去延伸了。而我们这时依次取出的木板最大宽度就是
，而我们只需要找出每个木板的
找出最大值即可。
还是不会的，建议结合题解和代码，手算验证一遍。为了好理解，专门使用了结构体，不然单个值其实就能解这道题。
PS：下面代码共有 C++普通STL实现， C++链表栈实现， JAVA Stack方法实现
时间复杂度：
C++普通STL实现
#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%ld",&x)
#define Scll(x) scanf("%lld",&x)
#define Pri(x) printf("%d\n",x);
#define Prl(x) printf("%lld\n",x);
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false)
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=1e5+5;
struct Node{
int val;
int lpos;
Node(int inval,int inlpos){
val = inval;
lpos = inlpos;
}
};
stack<Node> q;
int main(){
int n;
while(~Sca(n)&&n){
ll maxx=0;
For(i,1,n){
int num; Sca(num);
int pos=i;
while(!q.empty()&&num<=q.top().val){
tomin(pos,q.top().lpos);
tomax(maxx,(ll)(i-q.top().lpos)*q.top().val);
q.pop();
}
q.push(Node{num,pos});
}
while(!q.empty()){
tomax(maxx,(ll)q.top().val*(n-q.top().lpos+1));
q.pop();
}
Prl(maxx);
}
} C++链表栈实现
#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%ld",&x)
#define Scll(x) scanf("%lld",&x)
#define Pri(x) printf("%d\n",x);
#define Prl(x) printf("%lld\n",x);
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false)
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }
template <class T>void tomin(T&a,T b){ a=min(a,b); }
struct Stack{
Stack *front;
int val;
int lpos;
Stack(){
front = NULL;
val = 0;
lpos = 0;
}
Stack(int inval,int inlpos){
front = NULL;
val = inval;
lpos = inlpos;
}
}*tail;
int main(){
int n;
while(~Sca(n)&&n){
tail = new Stack;
ll maxx = 0;
For(i,1,n){
int num; Sca(num);
int pos = i;
Stack *now = tail->front;
while(now!=NULL&&num<=now->val){
tomin(pos, now->lpos);
tomax(maxx, (ll)now->val * (i-now->lpos));
tail->front = now->front;
delete now;
now = tail->front;
}
now = new Stack(num, pos);
now->front = tail->front;
tail->front = now;
}
Stack *now = tail->front;
while(now!=NULL){
tomax(maxx,(ll)now->val*(n - now->lpos + 1));
tail->front = now->front;
delete now;
now = tail->front;
}
Prl(maxx);
}
} JAVA Stack方法实现
import java.util.Scanner;
import java.util.Stack;
class Node{
int val;
int lpos;
Node(){}
Node(int inval, int inlpos){
val = inval;
lpos = inlpos;
}
}
public class Main {
public static void main(String[] args) {
int n;
Scanner sca = new Scanner(System.in);
Stack<Node> q = new Stack<Node>();
while(true) {
long maxx = 0;
n = sca.nextInt();
if(n == 0) break;
for(int i = 1; i <= n; ++ i) {
int num;
int pos = i;
num = sca.nextInt();
while(!q.empty()&&num<=q.peek().val) {
pos = Math.min(pos, q.peek().lpos);
maxx = Math.max(maxx, (long)q.peek().val * (i - q.peek().lpos));
q.pop();
}
q.push(new Node(num, pos));
}
while(!q.empty()) {
maxx = Math.max(maxx, (long)q.peek().val * (n - q.peek().lpos + 1));
q.pop();
}
System.out.println(maxx);
}
sca.close();
}
} 
京公网安备 11010502036488号