题解：B4273 [蓝桥杯青少年组省赛 2023] 最大的矩形纸片

· · 题解

题解：B4273 [蓝桥杯青少年组省赛 2023] 最大的矩形纸片

这题一眼就是单调栈嘛。

1. 解题思路

老规矩，我们先来算算样例：

样例输出是 8，也就是第 4 到第 5 列，高为 4 的矩形，面积是 8。

题目要求的就是上面这种图（下边固定）中最大矩形的面积。那我们思考一下，矩形面积是由一个底面长度乘上高所得来的。

解题的思路就是不妨固定一个高，求这个高的最长底面长度。具体一点，就是对于每一个竖列（假设高度是 h），算出第一个比它靠右并且低于它高度的（我们不妨设是第 r 列）和第一个比它靠左并且低于它高度的（设为第 l 列），求出所有竖列中 h \times [(r - 1) - (l + 1) + 1] 的最大值，也就是每个竖列 h \times (r - l - 1) 的最大值。

再思考一下，怎样算出第一个比它靠右并且低于它高度的和第一个比它靠左并且低于它高度的？

其实这就是单调栈解决的基本问题啦，不懂的可以去看看 【模板】单调栈，这里的问题就是现在解决的问题。只是这里需要两个单调栈维护（不是求左边的和右边，一共两个方向嘛）即可了。

2. 时间复杂度

对于单调栈，也就是预处理部分，每个元素都只进出栈一次，O(n) 时间复杂度（其实是自带二倍常数的，因为有两个单调栈）。

对于处理的部分，O(1) 查询第一个比它靠右并且低于它高度的和第一个比它靠左并且低于它高度的，一共遍历 n 次，总共时间复杂度 O(n)。

最后这个思路时间复杂度 O(n)，最优秀的时间复杂度啦。

3. 代码实现

就知道你们最想要这个。。。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
int n, a[maxn], l[maxn], r[maxn]; 
ll ans;
struct node { int idx, num; };
stack<node> lstk, rstk;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        while (lstk.size() && lstk.top().num > a[i]) {
            l[lstk.top().idx] = i;
            lstk.pop();
        }
        lstk.push(node({i, a[i]}));
    }
    for (int i = n; i >= 1; i--) {
        while (rstk.size() && rstk.top().num > a[i]) {
            r[rstk.top().idx] = i;
            rstk.pop();
        }
        rstk.push(node({i, a[i]}));
    }
    for (int i = 1; i <= n; i++) if (l[i] == 0) l[i] = n + 1;
    for (int i = 1; i <= n; i++) ans = max(ans, (ll)(l[i] - r[i] - 1) * (ll)a[i]);
    cout << ans << "\n";
    return 0;
}

自认为码风良好。（我是不是太自恋了？？？）

通过记录（不要质疑我～）