题目描述
给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积。
图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位
例如：给出的高度 =[2,1,5,6,2,3],返回10.
思路分析
可以依次遍历数组中的元素，可以知道较小的元素会成为矩形高的限制条件，比如遍历到1时，前一个数字是2,1会成为2、1这两个数字形成的矩形高度的限制条件，如果要形成宽度为2（也就是包含1和2的两部分）的矩形，其高度只能是1和2中的较小元素。遍历过程中遇到较大的元素不会成为其高度的限制条件。因此可以维护一个升序栈，当前遍历的元素如果大于栈顶指示的元素就直接将其入栈，小于栈顶元素的话就将栈顶元素出栈并且计算以栈顶元素为高能够形成的最大面积，这样就能够得到最大的矩形面积了。由于我们得知道矩形的宽度，故栈中放置的是数组元素的下标。
举例验证
假如给定的数组是{2,1,5,6,2,3}，申请一个栈st，i表示数组下标，最大面积maxArea，当前最大面积tmpArea，初始时都设置为0.
1、i=0时栈为空，先元素2入栈得到st(0)；
2、i=1时遍历到元素1，由于其小于栈顶指示的元素，故要先计算以栈顶元素能够形成的最大面积，将其出栈，此时栈空，矩形的宽度是(i-1-(-1))=1,当前面积是tmpArea=21，将其放入maxArea中。然后将i=1入栈，得到st(1);
3、i=2时遍历到元素5，大于栈顶元素，入栈即可，得到st(1,2)；接着i=3时遍历到元素6，大于栈顶元素，入栈即可，得到st(1,2,3)；
4、i=4时遍历到元素2，小于栈顶元素，出栈6，tmpArea=(i-1-2)6=6,更新maxArea=6，接着栈顶元素还是大于2，继续出栈5，tmpArea=(i-1-1)5=10,更新maxArea=10；然后将i=4入栈，得到st(1,4);
5、i=5时遍历到元素3，直接入栈得到st(1,4,5);
6、没有元素了，那么就去处理剩余栈中的元素，出栈5，tmpArea=(n-1-4)3=3,不用更新maxArea，接着出栈4，tmpArea=(n-1-1)2=8,不用更新maxArea，接着出栈1，tmpArea=(n-1-(-1))1=6,也不需要更新maxArea。最后得到最大面积是maxArea=10.
代码如下
int largestRectangleArea(vector<int>& height)
{
stack<int>st; //升序栈
int ret=0; //记录最大面积
for(int i=0;i<height.size();++i)
{
if(st.empty() || height[st.top()]<=height[i])
st.push(i); //栈空或者当前元素大于栈顶元素就入栈
else //栈顶元素大于当前遍历元素，右边界确定了，接着就去左边寻找宽度
{
while(!st.empty() && height[st.top()]>height[i])
{
int h=height[st.top()]; //以栈顶元素为高
st.pop();
int curlen=(i-1-(st.empty()?-1:st.top())); //当前长度
ret=max(ret,h*curlen);
}
st.push(i); //最后入栈
}
}
while(!st.empty())
{
int h=height[st.top()];
st.pop();
int curlen=(height.size()-1-(st.empty()?-1:st.top())); //当前长度
ret=max(ret,h*curlen);
}
return ret;
}复杂度分析
由于只需要遍历一次数组即可得到最大面积，故时间复杂度是O(n)；程序中维护了一个升序栈，栈中最多的元素个数可达到n，也就是数组中元素是升序的，这样空间复杂度就是O(n)。
暴力方法
当然本题还有一种暴力方法，其时间复杂度达到了O(n^2)级别，思路就是依次遍历数组中的元素，以当前元素为高往左往右扩展得到最大的宽度，来计算面积的方法。
代码如下
int largestRectangleArea(vector<int>& height)
{
int maxArea=0;
int tmpArea=0;
for(int i=0;i<height.size();++i)
{
int count=1;
int left=i-1,right=i+1; //分别往左往右延伸得到当前元素为高的最大宽度
while(left>=0)
{
if(height[i]<=height[left])
{
--left;
++count;
}
else
break;
}
while(right<height.size())
{
if(height[i]<=height[right])
{
++right;
++count;
}
else
break;
}
tmpArea=height[i]*count;
if(tmpArea>maxArea)
maxArea=tmpArea;
}
return maxArea;
}题目描述
给出n个数字，表示一个高程图，高程图中每一条的宽度为1，请计算下雨之后这个地形可以存储多少水
例如，给出[0,1,0,2,1,0,1,3,2,1,2,1],返回6.
思路分析
可以参考上面一题的方法，现在我们维护一个降序栈，这是因为只有当前高度小于前面的高度接着遇到了比当前高度更大的高度才可以形成容器存储水，故在此我们要维护一个降序栈。依次遍历数组，若当前元素小于栈顶元素，我们先不计算其能形成的面积，接着遍历数组即可。如果当前元素大于栈顶元素，那么这时就相当于找到了右边界，又由于栈是降序的，如果除了栈顶元素外还有元素，那么其左边界也就确定了，累加上其面积即可。在此过程中我们也要知道宽度，所以栈中存放的是数组元素的下标。
举例验证
假如给定的数组是{2,1,0,2}，现在要求其能存储的最大面积maxArea=0，当前面积tmpArea=0，降序栈st，cur指示刚出栈的元素，i是当前数组元素的下标位置。
1、i=0，此时栈空直接入栈，得到st(0)；接着i=1，小于栈顶元素，直接入栈，得到st(0,1)；接着i=2，还是小于栈顶元素，直接入栈，得到st(0,1,2)；
2、i=3,这时当前元素2大于栈顶元素，出栈cur=2，相当于给栈顶元素确定了右边界，tmpArea=(i-1-1)(min(A[i],A[st.top()])-A[cur])=1*1=1，maxArea累加上1得到1；接着栈顶元素还是小于当前元素，继续出栈cur=1，tmpArea=(i-1-0)(min(A[i],A[st.top()])-A[cur])=2(2-1)=2,maxArea累加上2得到3；接着栈顶元素等于当前元素，继续出栈，但是栈中已经没有元素了，也就是没了左边界了自然就不能存储水了，出栈即可。
*代码如下**
int trap(int *A, int n)
{
stack<int>st; //维护一个降序栈,栈中存放的是元素在数组中的下标
int ret = 0;
for (int i = 0; i < n; ++i)
{
while (!st.empty() && A[i] >= A[st.top()]) //如果栈不空且当前元素大于栈顶元素，那么就可以确定其右边界了
{
int cur = st.top();
st.pop(); //出栈
if (st.empty()) //出栈了一个元素然后栈为空，说明这时没了左边界，接着处理后续的元素
break;
else //不为空的话，就有左边界了，可以存储水
{
int width = (i - 1 - st.top());
ret += width*(min(A[i], A[st.top()]) - A[cur]); //左右边界的小值决定了高度
}
}
st.push(i); //入栈
}
return ret;
}复杂度分析
只需要遍历一次数组即可，时间复杂度是O(n),栈中最多会存放n个元素，故空间复杂度也是O(n)。
技巧方法
当然还有一种更为方便的方法来计算存储的水量，若要地形能够存储水，需要有左边界和右边界，还要求左边界和右边界不能挨在一起，这样{2,1,3}是可以存储水的，左边界取2，右边界取3，存储的水量为1(min(2,3)-1)=1,{1,2,3}是不可以存储水的，没有合适的左边界。这样我们得到启发，先找出数组中的最大元素，然后计算左半部分和右半部分的存储水量，加起来即可。对于左半部分（如果存在的话），他们的右边界一定是存在的，我们就可以设置一个变量left来表示其左边界，如果当前数小于left，那么就可以让left作为左边界先计算存储的水量，如果大于left就更新left，右半部分的处理类似处理。
*举例分析**
初始存储水量为maxArea=0,接着依次累加存储的水量
假如给定数组A[]={0,1,0,2,1,0,1,3,2,1,2,1}，我们可以先找到最大值3及其下标maxindex=7，接着分别计算左半部分和右半部分的存储水量。
对于左半部分数据，
1、初始设置left=0，开始遍历左半部分元素；
2、i=0时不用更新；
3、i=1，数组元素1大于left更新left=1；
4、i=2，数组元素0小于left计算存储水量left-A[i]=1,maxArea=1；
5、i=3，数组元素2大于left更新left=2；
6、i=4，数组元素1小于left计算存储水量left-A[i]=1，maxArea=2；
7、i=5，数组元素0小于left计算存储水量left-A[i]=2，maxArea=4；
8、i=6，数组元素1小于left计算存储水量left-A[i]=1，maxArea=5；
9、左半部分计算结束。
对于右半部分数据，要从右向左遍历计算，
1、初始设置right=0，开始遍历右半部分元素；
2、i=11，数据元素1大于right更新right=1；
3、i=10，数据元素2大于right更新right=2；
4、i=9，数据元素1小于right计算存储水量right-A[i]=1，maxArea=6；
5、i=8，数据元素2等于right，继续；
6、右半部分计算结束。
代码如下
int trap(int* A, int n)
{
int maxArea=0;
int maxpos=0; //数组A中最大值的下标
for(int i=1;i<n;++i)
{
if(A[i]>A[maxpos])
{
maxpos=i;
}
}
int left=0,right=0; //left表示左边已经遍历的点的最大值,right同理
//由于我们是在最大值的左右两边求面积，处理左边时，不用考虑右边界，同理处理右边时，
//不用考虑左边界
for(int i=0;i<maxpos;++i) //计算左边的面积
{
if(A[i]<left) //只要当前值小于left就可以直接计算当前单位的面积，因为右边界肯定没问题
maxArea+=(left-A[i]);
else
left=A[i]; //遇到了更大的值就要更新left
}
for(int i=n-1;i>maxpos;--i)
{
if(A[i]<right)
maxArea+=(right-A[i]);
else
right=A[i];
}
return maxArea;
}复杂度分析
先遍历一遍找到最大值，然后依次遍历左半部分和右半部分，所以时间复杂度是O(n)，没有使用额外空间，故空间复杂度是O(1)。
京公网安备 11010502036488号