POJ 2823

题意：给定一个大小已知的数组以及一个大小已知的滑动窗口，窗口每个时刻向后移动一位，求出每个时刻窗口中数字的最大值和最小值。

思路： 单调队列可以用来维护某一区间的最值。

1.从队尾插入元素：当有新元素需要入队时，让它与当前队尾元素进行比较，若它小于等于当前队尾元素（即破坏了原队列的单调性），那么删除队尾元素，并继续比较队尾与新元素，直到找到一个队尾大于新元素时，将新元素插入到队尾。被删除的元素既比新元素大，又会比新元素先滑出窗口，因此肯定不会成为答案。这个操作不断维护了队列中的最值。

2.删除队首元素：由于序列中的元素当且仅当在滑动窗口时有效，因此，当队首元素不在滑动窗口内时，就删除队首元素。这个操作维护了数据的临时性。

双端队列（deque）常用函数：

deq.front()：返回第一个元素的引用。

deq.back()：返回最后一个元素的引用。

deq.push_front(x)：把元素x插入到双向队列的头部。

deq.pop_front()：弹出双向队列的第一个元素。

deq.push_back(x)：把元素x插入到双向队列的尾部。

deq.pop_back()：弹出双向队列的最后一个元素。

代码（POJ不开O2用STL就是慢…所以用了两个队列）：

struct node
{
    int v,id;
};
int a[1000010];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    deque<node>q;
    node temp;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)//维护一个单调递增队列求最小值
    {
        temp.v=a[i];
        temp.id=i;
        if(!q.empty())
        {
            if(q.back().v<=temp.v)
                q.push_back(temp);
            else
            {
                while(!q.empty()&&q.back().v>temp.v)
                    q.pop_back();
                q.push_back(temp);
            }
        }
        else q.push_back(temp);
        if(i-q.front().id>k-1)q.pop_front();
        if(i>=k-1)
        {
            if(i!=n-1)printf("%d ",q.front().v);
            else printf("%d\n",q.front().v);
        }
    }
    deque<node>Q;
    for(int i=0;i<n;i++)//维护一个单调递减队列求最大值
    {
        temp.v=a[i];
        temp.id=i;
        if(!Q.empty())
        {
            if(Q.back().v>=temp.v)
                Q.push_back(temp);
            else
            {
                while(!Q.empty()&&Q.back().v<temp.v)
                    Q.pop_back();
                Q.push_back(temp);
            }
        }
        else Q.push_back(temp);
        if(i-Q.front().id>k-1)Q.pop_front();
        if(i>=k-1)
        {
            if(i!=n-1)printf("%d ",Q.front().v);
            else printf("%d\n",Q.front().v);
        }
    }
    return 0;
}

HDU1506

题意：给一个由几个相连接的矩形组成的多边形，计算多边形包含的最大的矩形的面积。

思路：要想找到里面的最大的面积，我们可以对每一个矩形的高度为标准，尽量的向两头扩展，这样就可以找出以它高度为标准的，并包含它本身的最大矩形。要将其扩展过去，必须高度不低于当前扩展点的高度。

单调栈可以很方便地求出某个数的左边或者右边第一个比它大或者小的元素。

从左到右遍历，对于当前矩形，如果高度比栈顶大或相等，就放入栈中，如果高度比栈顶小，就让栈顶退栈，因为该元素比栈顶元素更靠近后面的元素，而且比栈顶元素更小，所以更优，这样直到栈顶高度小于等于该矩形，那么所退的元素的右边第一个比它小的元素就是该矩形。找左边的同理，从右边开始遍历。

代码：

typedef long long ll;
int h[100010];
int l[100010],r[100010];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)break;
        for(int i=1;i<=n;i++)
            scanf("%d",&h[i]);
        ll ans=0;
        stack<int>s;
        for(int i=1;i<=n;i++)
        {
            l[i]=0;
            while(!s.empty()&&h[i]<=h[s.top()])
                s.pop();
            if(!s.empty())l[i]=s.top();
            s.push(i);
        }
        while(!s.empty())s.pop();
        for(int i=n;i>=1;i--)
        {
            r[i]=n+1;
            while(!s.empty()&&h[i]<=h[s.top()])
                s.pop();
            if(!s.empty())r[i]=s.top();
            s.push(i);
        }
        ll temp;
        for(int i=1;i<=n;i++)
        {
            temp=1ll*h[i]*(r[i]-l[i]-1);
            ans=max(ans,temp);
        }
        printf("%lld\n",ans);
    }
    return 0;
}