201312-3最大的矩形

题目

题目链接

image-20211112173121397

思路

我们可以这样求出我们的最大矩形: 对于任意一个矩形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上面找了答案,然后发现它们贴的标签是单调栈,至于什么是单调栈,现在我还没明白(因为没有去搜),所以这里先做一下标记,等我想起来了在来补充一下单调栈的东西。

0%