Largest Rectangle in a Histogram HDU - 1506 (DP 单调栈 思维) 详细题解

题意: 给出若干连续的矩形高度(如图), 宽度为1, 求最大的矩形面积

题解: 这是一道非常不错的题目, 简单总结一下这类题的惯用思路
对于这种拿到就有思路的题目, 我们不妨先考虑惯用思路, 也就是枚举每一个hi, 再分别左右扫描, 很显然n^2的复杂度, 一定会超时, 我们不妨再来考虑哪里可以拿来优化.
这一个思路超时的关键就在于里面似乎存在了大量的重复计算, 可以试想扫描hi高度时, 很多比较已经在hi-1扫描过了, 所以我们需要减少重复计算, 毫无疑问就要采用空间来换时间咯.
对于区间求最值的优化, 我们可以采用dp或单调栈/单调队列优化

• 定义Li, Ri为以hi为最低点时, 左右不小于hi的最远坐标(包括其自身)
• 使用dp或单调栈优化
• 求得max( h[i]*(r[i]-l[i]+1) )即为答案

dp版本, 状态转移方程为l[i] = {l[ l[i]-1 ] | h[ l[i]-1 ] >= h[i] }, r[i] = {r[ r[i]+1 ] | h[ r[i]-1 ] >= h[i] }

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 1e5+10;

int n, h[maxn];
int l[maxn], r[maxn]; //以hi为最低点左右最远不小于hi的坐标
int main()
{
    while(cin >> n && n){
        for(int i = 1; i <= n; i++){
            cin >> h[i];
            l[i] = r[i] = i; //初始化
        }

            for(int i = 2; i <= n; i++){
                //向左遍历直至发现小于hi的点, 同时避免重复计算
                while(h[l[i]-1] >= h[i] && l[i]>0)
                    l[i] = l[l[i]-1];
            }
            for(int i = n-1; i > 0; i--){
                //向右遍历直至发现小于hi的点, 同时避免重复计算
                while(h[r[i]+1] >= h[i] && r[i]<n)
                    r[i] = r[r[i]+1];
            }
            LL ans = 0;
            for(int i = 1; i <= n; i++)
                ans = max(ans, (LL)h[i]*(r[i]-l[i]+1));
            cout << ans << endl;
    }

	return 0;
}

单调栈版本

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 100000 + 100;
stack<int> S;
ll h[N];
int R[N], L[N]; //以hi为最低点左右两边最远不小于其的坐标

int main() {
    int n;
    while(~scanf("%d", &n) && n) {
        for(int i = 1 ; i <= n ; i++)
            scanf("%I64d", &h[i]);

        while(S.size())
            S.pop();

        //利用单调栈取得以hi为最低点的左右边界
        for(int i = 1 ; i <= n ; i++) {
            while(S.size() && h[S.top()] >= h[i])
                S.pop();

            if(S.empty())
                L[i] = 1;
            else
                L[i] = S.top()+1;
            S.push(i);
        }

        while(S.size())
            S.pop();
        for(int i = n; i > 0 ; i--) {
            while(S.size() && h[S.top()] >= h[i])
                S.pop();

            if(S.empty())
                R[i] = n;
            else
                R[i] = S.top()-1;

            S.push(i);
        }

        ll ans = 0;
        for(int i = 1 ; i <= n ; i++) {
            ans = max(ans, h[i] * (R[i]-L[i]+1));
        }
        printf("%I64d\n", ans);
    }
    return 0;
}