题目链接 POJ2559
一.思路分析：
我看到题目的第一想法，就是木桶效应，由短板确定，所以遍历求出数组中长最短的矩形，乘数组长度即为答案。但是思考一下后，发现这种思路是错误的。例如下图：
反例短板为1，则框出矩形面积为5，但是若仅框出长为10的一个矩形，则面积为10，大于5，可见思路错误。
仔细分析一下，就可以发现，对于每个矩形i，如果框出的矩形要完全包含这个矩形，就需要找出它左边和右边第一个比它长度短的矩形，用矩形i的长度乘这段区间的长度，即为完全包含矩形i的最大矩形面积。所以，题目就可以表述为，求每一个矩形i左端和右端第一个比它小的矩形，并计算框出矩形的最大面积area[i]，枚举0<=i<n的每个矩形，找出最大的area[i]，即为答案。
二、解题方案：
有了上面的思路，目的就明确了：将每个矩形长存入数组，并求数组中每个元素左边和右边第一个比它小的数的下标。我共想出了三种方案，列举如下：
1.分治（TLE）
2.利用优先队列和红黑树，即使用STL容器priority_queue和set（TLE）
3.利用栈（AC）
三、具体介绍：
解法一：
我联想到另一道题目：求数组最大和连续子序列。解法一思路和这题类似，对于数组中每个元素，最大值的取值有三种情况：全部在这个元素左边，全部在这个元素右边，包含这个元素。因此利用分治的思想，递归左边求最大值；递归右边求最大值；遍历数组求出这个元素左边和右边第一个比它小的元素，用元素值成区间长度；最大值即为这三个值的最大值。虽然最好情况下时间复杂度为O(nlogn)，但是最坏情况时间复杂度为O(n^2)，并不比暴力求解好多少，不出意料，TLE（而且从解法二看出，即使O(nlogn)的复杂度仍然TLE）。
解法一关键代码 解法二：
由于这一题的思路很明确，所以要做的就是降低时间复杂度。所以我采用了优先队列和set。对于数组中每个元素a[i]，需要知道左右第一个比它小的元素，所以只要从最小的元素开始寻找即可。因此我采用了优先队列，O(n)时间构建一个小根堆，每次取最小元只要O(1)，维护小根堆性质每次需要O(logn)时间，因此总时间为O(nlogn)。
而set里存储的是小于等于当前堆根元素的元素下标，初始set里存-1和n（下文解释原因）。因为set中全部是比堆根元素还要小的元素下标，所以每次查询堆根处的元素的下标在set里相邻的两个元素，就是左右第一个比它小的元素，如果左右侧没有比它小的元素，就可以认为左右侧的下标为-1和n。（解释的很乱，下面上图）
比如数组a[4]={1,4,2,3}（为了直观，set画成数组形式，不画成树）
第三行为要求出的数据
set初始情况
堆根1的下标0入set
堆根2的下标3入set
堆根3的下标2入set
堆根4的下标1入set由此看出，set中第一个比堆根下标小和第一个比堆根下标大的元素就是要求的区间界，可以用upper_bound()函数来查询，时间复杂度也为O(nlogn)，最后再遍历一遍数组，求出元素值成区间长度的最大值，因此总时间复杂度为O(nlogn)。做出来这种方法，我本以为肯定可以AC，没想到，TLE。
结构体定义和重载运算符
解法二关键代码 解法三：
解法二的TLE，是出乎我的意料的，甚至让我产生了我的思路是否正确的怀疑。但是经过分析，我认为思路是没有问题的，也就是说，存在O(n)的算法，可以求出每个元素左侧和右侧第一个比它小的元素下标。于是，我想到了利用栈。简单介绍一下，题目的原形，是求数组每个元素右侧比它大的第一个元素。做法就是构建一个栈，初始栈为空。从数组最后一个元素开始反向遍历，如果栈空，则右侧没有比它大的元素；或栈顶大于该元素，则右侧比它大的元素就是栈顶。否则一直出栈。（讲不清就上图）
例如数组a[5]={4,1,5,2,3}
第二行为要求结果从数组最后一个元素反向遍历，由于此时栈为空，所以3右边没有比它大的元素，即为-1，然后3入栈。
3入栈由于栈顶3大于2，所以2右侧第一个比它大的元素为3，2入栈。
2入栈由于5大于栈顶，出栈，直到栈为空，因此5右侧没有比它大的元素，为-1。
2 3 出栈，5入栈由于栈顶5大于1，所以1右侧第一个比它大的元素为5，1入栈
1入栈由于栈顶1小于4，出栈；栈顶5大于4，所以4右侧第一个比它大的元素为5，4入栈
1出栈，4入栈此时遍历完成，算法结束，时间复杂度为O(n)。
上述算法关键代码所以，能求右侧第一个比它大的元素，当然就能求第一个比它小的元素，也就能求左侧第一个比它小的元素。分析到这里，问题解决——遍历两次数组，O(n)时间求出每个元素左右第一个比它小的元素下标，再O(n)遍历一遍，求出元素值乘区间长度的最大值，总时间为O(n)。果然，AC。下附代码
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
struct LR
{
int l;int r;//构建结构体数组，l r分别为当前元素左右第一个比它小的元素下标
};
int main()
{
int num;
vector<long long int> res;//多组输入
while(1)
{
int *inbox;
LR *lr;
cin>>num;
if(num==0)
{
break;
}
inbox=new int[num];
lr=new LR[num];
for(int i=0;i<num;i++)
{
cin>>inbox[i];
}
//遍历两遍，求每个元素左右第一个比它小的元素下标
stack<int> s;
for(int i=num-1;i>=0;i--)
{
while(!s.empty()&&inbox[i]<=inbox[s.top()])
{
s.pop();
}
if(s.empty())
{
lr[i].r=num;
}
else
{
lr[i].r=s.top();
}
s.push(i);
}
while(!s.empty())
{
s.pop();
}
for(int i=0;i<num;i++)
{
while(!s.empty()&&inbox[i]<=inbox[s.top()])
{
s.pop();
}
if(s.empty())
{
lr[i].l=-1;
}
else
{
lr[i].l=s.top();
}
s.push(i);
}
//再遍历一遍，求最大值，即为答案
long long int m=0;
for(int i=0;i<num;i++)
{
if(m<(long long int)inbox[i]*(lr[i].r-lr[i].l-1))
{
m=(long long int)inbox[i]*(lr[i].r-lr[i].l-1);
}
}
res.push_back(m);
delete []inbox;
delete []lr;
}
for(int i=0;i<res.size();i++)
{
cout<<res[i]<<endl;
}
}
AC记录（忽略我的打码） 小感想：
1.基础数据结构不见得没法做赛题。在这一题中，栈这种家喻户晓的数据结构，竟然比优先队列和红黑树更加优秀，所以我很希望能多做到这类题，增加我对每种数据结构的理解，而不是仅仅知道很多数据结构，但都浅尝辄止。
2.不要轻易放弃。其实我昨晚解法二，已经想要放弃了，但是我还是说服自己，再想想，终于，解决了问题。
网友评论