51Nod 1102 面积最大的矩形 +1272 最大距离单调栈

记笔记记笔记：对于区间最值与区间长度/和等的问题，用单调栈来维护区间端点。

这里来补一补单调栈和单调队列的基础知识：

单调栈： //单调递增（减）栈：从栈顶到栈底为单调递增（减）

单调栈解决的是以某一值为区间最值的最大区间的问题，实现方法：维护一个单调递增（减）的栈，当遇到比栈顶元素大（小）的元素准备入栈时，开始跳栈，直到栈顶元素大于（小于）当前元素。跳栈结束后开始更新当前元素的区间（无论是否有跳栈操作，都要更新区间）。

单调队列：

单调队列解决的是区间最值的问题，实现方法：维护一个单调递增（减）的双端队列，队列中保存原始序列的标号，当将要入队的元素比队尾元素小（大）时，队尾开始出队，直至当前元素大于（小于）队尾元素，当入队元素与队首元素跨度大于规定区间时，队首开始出队，直至符合区间要求。可以保证队首元素为区间最小（大）值，但不能保证队尾为原始序列中的最大（小）值，同时维护了区间长度。

#include<iostream> //这里用的是单调递减栈
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
struct squre{
    long long l,r,h;
};
stack<squre>a;
int n;
squre b,c,ans[50005];
int main()
{
    cin >> n;
    if (n == 0)
        cout << "0" << endl;
    else
    {
        int cnt = 0;
        cin>>b.h;
        b.l = 0; b.r = 1;
        a.push(b);
        for (int i = 1; i < n; i++)
        {
            c.h=0;            //记录是否更新栈顶元素
            cin >> b.h;
            while (!a.empty() && a.top().h > b.h)  //准备入栈元素高度<栈顶元素，出栈
            {
                a.top().r=i;
                ans[cnt++] = a.top();             //记录区间无法继续延伸的元素
                c = ans[cnt - 1];
                a.pop();
            }
            if (c.h != 0)               //更新当前元素区间
            {
                b.l = !a.empty() && a.top().h == b.h ? a.top().l : c.l;
            }
            else
            {
                b.l = !a.empty() && a.top().h == b.h ? a.top().l : i;
            }
            b.r = i + 1;
            a.push(b);
        }
        while (!a.empty())   //全部出队
        {
            a.top().r = n;
            ans[cnt++] = a.top();
            a.pop();
        }
        long long res = 0;
        for (int i = 0; i < n; i++)  //记录面积最大值
        {
            res = max(res, ans[i].h*(ans[i].r - ans[i].l));
        }
        cout << res << endl;
    }
    return 0;
}

1272 最大距离

相对上面的题，这个题要简单很多，用一个单调栈来维护最大区间，一个栈来保存跳栈的数据，每次跳栈的时候记录一下，数据处理完重新入栈。

//有毒……这个题……#21一直TLE，orz ……有米有大佬指点一下

#include<iostream>
#include<string>
#include<stack>
#include<algorithm>
using namespace std;
struct node {
    int v, id;
};
stack<node>save, now;
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        node a;
        a.id = i;
        cin >> a.v;
        if (now.size()==0 || a.v < now.top().v)
            now.push(a);
        else
        {
            while (!now.empty()&&now.top().v <= a.v)
            {
                ans = max(ans, i - now.top().id);
                save.push(now.top());
                now.pop();
            }
            while (!save.empty())
            {
                now.push(save.top());
                save.pop();
            }
        }
    }
    cout << ans << endl;
    return 0;
}

51Nod 1102 面积最大的矩形 +1272 最大距离 单调栈

51Nod 1102 面积最大的矩形 +1272 最大距离单调栈