201312-3最大的矩形

lyc 收录于 CCF-CSP

2021-11-13 2021-11-13 约 515 字预计阅读 2 分钟 - 条评论

题目

思路

我们可以这样求出我们的最大矩形：对于任意一个矩形h[i]，我们就以它作为高，求出以它为基准的最大的矩形面积。具体怎么做呢？我们可以向左找出比它高的矩形并且是连续的（意思是中间没有一个比它小的），那这样子是不是可以形成一个扁长矩形？同样的，向右找出比它高的矩形并且是连续，那么，以h[i]作为高的最大矩形的面积等于多少不就可以算出来了吗？那我们依次遍历这样的矩形，最大的矩形面积自然也就可以找出来了。

如果不是很能理解的话，看看代码应该就能够懂得了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


/* 最大的矩形 */
#include <bits/stdc++.h>
using namespace std;
int n;
int h[1000 + 10], d[1000 + 10];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    int maxn = 0;
    for (int i = 0; i < n; i++) {
        int j = i, k = 1;  // k用于表示以h[i]为高的最大矩形的宽
        while (j - 1 >= 0 && h[j - 1] > h[i]) {
            k++, j--;
        }
        j = i;
        while (j + 1 < n && h[j + 1] > h[i]) {
            k++, j++;
        }
        maxn = max(maxn, h[i] * k);
    }
    cout << maxn;
    return 0;
}

后话

刚开始的时候自己比较懒，又或者自己确实比较菜，就是感觉做不出来，然后就是不想动手写。就去CSDN上面找了答案，然后发现它们贴的标签是单调栈，至于什么是单调栈，现在我还没明白（~~因为没有去搜~~），所以这里先做一下标记，等我想起来了在来补充一下单调栈的东西。