直方图中最大的矩形

暴力思路

枚举每一个元素,以此元素作高度, 向元素两边扩展, 分别知道第一个小于此数的数的下表, 左右下表的宽度就是矩形的宽度,因为每次需要向两边枚举, 所以时间复杂度是(On^2);

单调栈优化

每次需要向两边枚举,太耗时间, 如果用单调栈每次记录矩阵左边界和右边界的值,可以将时间复杂度控制在(On)

C++代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
long long  a[N], r[N], l[N], s[N];
int n, top1, top2;
vector<PII> mst1, mst2;

int main()
{
    while(cin >> n, n)
    {
        //初始化
        top1 = -1;
        top2 = -1;
        mst1.clear();
        mst2.clear();
        //输入数据
        for(int i = 0; i < n; i++) cin >> a[i];
        //左单调栈,记录每个元素从右至左第一个比此元素小的数的下标;
        for(int i = 0; i < n; i++)
        {
            while(top1 != -1 && mst1[top1].first >= a[i])
            {
                top1--;
                mst1.pop_back();
            }
            if(top1 != -1) l[i] = mst1[top1].second;
            else l[i] = -1;
            mst1.push_back({a[i], i});
            top1++;
        }
        //右单调栈, 记录每个元素从左至右第一个小于此数的数的下标;
        for(int i = n - 1; i >= 0; i--)
        {
            while(top2 != -1 && mst2[top2].first >= a[i])
            {
                top2--;
                mst2.pop_back();
            }
            if(top2 != -1) r[i] = mst2[top2].second;
            else r[i] = n;
            mst2.push_back({a[i], i});
            top2++;
        }

        long long mx = 0;
        for(int i = 0; i < n; i++)
        {
            s[i] = (r[i] - 1 - l[i]) * a[i];//以此元素的高度作为矩阵的高度, 向两边扩展, 最后一个合法的下标即为左边界或右边界
            mx = max(mx, s[i]);
        }
        cout << mx << endl;

    }
    return 0;
}