AcWing 131. 直方图中最大的矩形    原题链接    简单

作者： 作者的头像   Value ,  2020-09-03 09:49:22 ,  所有人可见 ,  阅读 610

2 


#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
int h[N], q[N], l[N], r[N];
int main(){
    int n;
    while(cin >> n, n){
        for(int i = 1; i <= n; i ++ )   cin >> h[i];
        h[0] = h[n + 1] = -1;
        int tt = 0;
        q[tt] = 0;
        /**  依次和单调栈内的“元素”比较（有效比较 **/
        /**  找到左边第一个比自己小的元素下标  **/
        for(int i = 1; i <= n; i ++ ){
            while(h[q[tt]] >= h[i]) tt -- ;
            l[i] = q[tt];
            q[ ++ tt] = i;
        }
        /** 找到右边第一个比自己小的元素下标   **/
        tt = n + 1, q[tt] = n + 1; 
        for(int i = n; i ; i -- ){
            while(h[q[tt]] >= h[i])  tt -- ;
            r[i] = q[tt];
            q[ ++ tt] = i;
        }
        ll res = 0;
        /**  l[i] 与 r[i] 内的元素均不能取  **/
        for(int i = 1; i <= n; i ++ )   res = max(res, (ll)h[i] * (r[i] - l[i] - 1));
        cout << res << endl;
    }
}

5 评论

用户头像
楚天   2020-10-29 12:59         踩      回复 
 tt = n + 1, q[tt] = n + 1;

大佬，这个里面的tt=n+1不是很理解，为什么要赋成n+1,而不能赋成0

用户头像
楚天   2020-10-29 13:58         踩      回复

大佬我试了，其实后面的tt不赋成n+1也可以，只要在while循环中加一个

while(tt&&a[q[tt]]>=a[i])

就行

用户头像
Value   2022-01-17 11:53         踩      回复

赋成0也是可以的，q[0]和q[n+1]一开始就是为了方便写循环把他们的值赋值成-1；其实可以直接用stack来存储会更好理解，这个用数组模拟栈我也不好理解

用户头像
楚天   2020-10-29 12:48         踩      回复

这个写的好清楚

用户头像
Value   2022-01-17 12:19         踩      回复 
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll height[N], l[N], r[N];
int main(){
    int n;  
    while(cin >> n && n){
        stack<ll> stk;
        for(int i = 1; i <= n; i ++ )    scanf("%lld", &height[i]);
        height[0] = -1;
        stk.push(0);
        for(int i = 1; i <= n; i ++ ){
            while(height[stk.top()] >= height[i])    stk.pop();
            l[i] = stk.top() + 1;
            stk.push(i);
        }
        height[n + 1] = -1;
        stk.push(n + 1);
        for(int i = n; i ; i -- ){
            while(height[stk.top()] >= height[i])    stk.pop();
            r[i] = stk.top() - 1;
            stk.push(i);
        }
        ll maxv = 0;
        for(int i = 1; i <= n; i ++ )   maxv = max(maxv, height[i] * (r[i] - l[i] + 1));
        cout << maxv << endl;
    }
    return 0;
}