柱状图最大矩形（更新中）

柱状图最大矩形（更新中）

柱状图最大矩形

给定$n$个非负的整数（$10\leq n\leq10000$）,表示柱状图中的矩形高度,宽度都是$1$.求柱状图中最大的矩形面积.

规定

以柱形图第一个柱形的底边左端点为原点建立坐标系.

以下所有小写字母都是非负整数.

对于$1\leq k\leq n$,设第$k$个柱形高度为$h_k$,则$R_k=\{(x,y):k-1\leq x\leq k,0\leq y\leq h_k\}$.

为方便起见,我们补充定义$h_0=,h_{n+1}=0,h=\max\limits_{1\leq k\leq n}{h_k}$.

定义柱状图$R=\bigcup\limits_{k=1}^{n}R_k$.

定义$[i,j,h]=\{(x,y):i-1\leq x\leq j,0\leq y\leq h,1\leq i\leq j\leq n,h\geq 0\}$ 为矩形.

若$[i,j,h]\subseteq R$,称之为有效矩形.

定义$E=\{[i,j,h]:[i,j,h]\subseteq R\}$为有效矩形集. $[i,j,h]\in E\Leftrightarrow\forall i\leq k\leq j(h\leq h_k)$

定义$S([i,j,h])=h(j-i+1)$为矩形的面积.

对集合$X$,定义$\max(X)$为$X$中的最大元素.特别地,定义$\max(\varnothing)=0$.

$\max(S(E))$即为所求的结果.

思路1 枚举 $O(n^2)$

对于$[i,j,h]\in E$,若$h_{i-1}<h,h_{j+1}<h,\exists i\leq k\leq j(h=h_k)$,我们称其为极大矩形.

设所有极大矩形构成的集合为$H$.故$H\subseteq E,\max(S(H))=\max(S(E))$

对于$1\leq k\leq n$,定义$E_k=\{[i,j,h_k]:[i,j,h_k]\in E,i\leq k\leq j\}$.

设$E_k\cap H=\{[i_0,j_0,h_k]\}$.

因此$i_0=\max(\{i:h_{i-1}<h_k,i\leq k\}),j_0=i_0=\max(\{j:h_{j+1}<h_k,j\geq k\})$ .

再考虑$\max\limits_{1\leq k\leq n}S(E_k\cap H)$ 即可.

#include <stdio.h>
int main()
{
    int n,i,j,k,m=0;
    scanf("%d",&n);
    int a[n+2];
    for (i=1;i<=n;i++) scanf("%d",a+i);
    a[0]=0,a[n+1]=0;
    for (k=1;k<=n;k++)
    {
        i=k,j=k;
        while (a[i-1]>=a[k])i--;
        while (a[j+1]>=a[k])j++;
        m=(m>(j-i+1)*a[k])?m:(j-i+1)*a[k];
    }
    printf("%d",m);
    return 0;
} 

思路2 动态规划 $O(nh)$

对于$1\leq x\leq n,1\leq y\leq h$,考虑函数$f(x,y)=\max(S(\{[i,x,y]:[i,x,y]\in E\}))$ .

当$1\leq y\leq h_1$时,$f(1,y)=y$；当$h_1< y\leq h$时,$f(1,y)=0$.

当$2\leq x\leq n$时,考虑转移方程：

​ 当$1\leq y\leq h_x$时,$f(x,y)=f(x-1,y)+y$；当$h_1< y\leq h$时,$f(x,y)=0$.

因此我们考虑$\max\limits_{1\leq x\leq n}\max\limits_{1\leq y\leq h}f(x,y)$即可.

#include <stdio.h>
int main()
{
    int n,i,j,m,h=0;
    scanf("%d",&n);
    int a[n],b[n];
    for (i=0;i<n;i++) 
    {
        scanf("%d",a+i);
        h=(h>a[i])?h:a[i];
    }
    for (i=0;i<a[0];i++) b[i]=1;
    for (i=a[0];i<h;i++) b[i]=0;
    m=a[0];
    for (i=1;i<n;i++)
    {
        for (j=0;j<h;j++)
        {
            if (j<a[i]) b[j]++;
            else b[j]=0;
            m=(m>b[j]*(j+1))?m:b[j]*(j+1);
        }
    }
    printf("%d\n",m);   
    return 0;
} 

思路3 单调栈 $O(n)$

对于$[i,j,h]\in E$,若$h_{j+1}<h,\exists i\leq k\leq j(h=h_k)$,我们称其为右极大矩形.

设所有极大右矩形构成的集合为$T$.故$T\subseteq E,\max(S(T))=\max(S(E))$

对于$1\leq k\leq n$,定义$G_k=\{[i,k,h]:[i,k,h]\in E\}\cap T$.

为方便起见.接下来将$h_i$记为$h(i)$.

我们构造一个栈$stack[0]=0$,然后按一下规则依次将柱形的编号放入栈中.设正准备入栈的编号为$k$.

​ 若$h(k)\geq h(stack[top])$.则$k$入栈.

​ 若$h(k)<h(stack[top])$.我们将栈中的元素依次出栈.直到$h(k)\geq h(stack[top])$.再将$k$入栈.

最后再将所有元素弹出栈.

我们分析一下这个栈的性质

​ 栈的元素是单调递增的.

​ 每个编号恰入栈出栈各一次.

​ 设当$k$入栈时$i=stack[m],m>1$出栈,则$\forall stack[m-1]<j<k(h(j)\leq h(i))$,因此$[stack[m-1]+1,k,h_i]\in G_k$,进一步可以证明这其中包含了$S(G_k)$的最大值.

​ 因此我们只需要在每次出栈时更新$\max$即可.

#include <stdio.h>
int main()
{
    int n,i,t=0,m=0;
    scanf("%d",&n);
    int a[n],b[n];
    for (i=0;i<n;i++) scanf("%d",a+i);
    b[0]=-1;
    for (i=0;i<n;i++)
    {
        while (a[i]<a[b[t]]&&t)
        {
            m=(m>a[b[t]]*(i-b[t-1]-1))?m:a[b[t]]*(i-b[t-1]-1);
            t--;
        }       
        t++;
        b[t]=i;
    }
    while (t)
    {
        m=(m>a[b[t]]*(n-1-b[t-1]))?m:a[b[t]]*(n-1-b[t-1]);
        t--;
    }
    printf("%d\n",m);   
    return 0;
} 

 动态规划 单调栈 枚举