枚举扩展朴素解法

这道题的正解是 $单调栈$ 求无交换最大矩形，再用 $稀疏表RMQ$ 处理至多一次交换，但是我们用朴素解法 $O(n^2)$ 向左右扩展（并可枚举一次交换）也能在考试时拿到一定的分数。

题意：直方图有 $n$ 根宽为 $1$ 的柱子，高度为 $h_i$ 。允许至多交换任意两根柱子的高度一次，求能勾勒出的最大矩形面积。

朴素做法：

无交换：把每个下标 $i$ 当作矩形高度，向左、向右扩展到高度 $<h_i$ 为止，面积为 $h_i\times(R-L+1)$ ，对所有 $i$ 取最大。时间 $O(n^2)$ 。

题目内容

小华之前玩过一个游戏，在横轴上放了 $n$ 个相邻的矩形，每个矩形的宽度是 $1$ ，而第 $i(1≦i≦n)$ 个矩形的高度为 $h_i$ ，这 $n$ 个矩形构成了一个直方图，在直方图中找出能够勾勒出来的矩形的最大面积。

这个游戏小华已经玩得很腻了，于是小华就想增加一下难度，现在有 $1$ 次交换任意 $2$ 个矩形的操作，请问在交换后，能够勾勒出的最大的短形面积能达到多少呢?

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写

选择提交后点击「开始AI分析」