acwing-3194 最大的矩形

acwing-3194 最大的矩形

这个题程序设计课上有讲过，

平民算法，时间复杂度在$O(n^2)$

//
// Created by HUAWEI on 2024/10/28.
//
#include<iostream>using namespace std;const int Max_size = 1e4 + 20;int N;
int h[Max_size];int main() {cin >> N;for (int i = 0; i < N; i++)cin >> h[i];int res = 0;for (int i = 0; i < N; i++) {int l = i - 1;int r = i + 1;while (l >= 0 and h[l] >= h[i])l--;while (r <= N - 1 and h[r] >= h[i])r++;int temp = (r - l - 1) * h[i];if (temp > res)res = temp;}cout << res << endl;return 0;
}

单调栈解决，时间复杂度在$O(n)$

//
// Created by HUAWEI on 2024/10/28.
//
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>using namespace std;int largestArea(vector<int> &h) {// 单调栈返回最大矩形面积stack<int> s; //单调非减栈h.insert(h.begin(), -1);h.push_back(0);int len = h.size();int res = 0;s.push(0);for (int i = 1; i < len; i++) {while (h[i] < h[s.top()]) {int temp = s.top();s.pop();res = max(res, (h[temp] * (i - s.top() - 1)));}s.push(i);}return res;
}int main() {int n;vector<int> h;cin >> n;for (int i = 0; i < n; i++) {int temp;cin >> temp;h.push_back(temp);}cout << largestArea(h);return 0;
}

参考博客