输入 每组第一个数N(0<=N<=20000)表示N个矩形。下面N行有两个数a(1 <= a <=1000),b(1 <= b<=1000)分别表示每个矩形的x轴长度和y轴长度。 输出 输出最大的面积
时间: 2023-08-11 20:06:31 浏览: 196
好的,以下是修改后的C++代码实现过程,已加上注释:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4 + 10;
ll n, a, b, st[N], top = 0, ans = 0;
int main() {
while (cin >> n) {
if (n == 0) break; // 当输入的 n 为 0 时,结束程序
top = 0; // 清空栈
ans = 0; // 重置最大矩形面积
for (int i = 1; i <= n; i++) { // 输入每个矩形的长宽
cin >> a >> b;
ll h = b; // 将矩形的高度赋值给 h
while (top && h < st[top]) { // 单调栈处理,如果当前矩形高度比栈顶元素低,说明栈顶元素的最大矩形面积已经确定
ans = max(ans, st[top] * (i - st[top - 1] - 1)); // 计算栈顶元素的最大矩形面积
top--; // 弹出栈顶元素
}
st[++top] = i; // 将当前矩形的下标加入单调栈
}
while (top) { // 处理栈中剩余的元素
ans = max(ans, st[top] * (n - st[top - 1])); // 计算栈顶元素的最大矩形面积
top--; // 弹出栈顶元素
}
cout << ans << endl; // 输出最大矩形面积
}
return 0;
}
```
注:本算法使用单调栈(Monotone Stack)实现,时间复杂度为 O(n)。
阅读全文