题意:求一个长为 n(1 <= n <= 100000) 的直方图的最大子矩形的面积。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1506
——>>暴力枚举每个位置的左边界和右边界,时间复杂度为O(n ^ 2)。。T_T。。
还是枚举每个位置的左边界和右边界,但用 dp 来优化。。时间复杂度大大降低。。
状态:L[i] 表示第 i 个位置的左边界。
状态转移方程:L[i] = L[L[i] - 1];
状态:R[i] 表示第 i 个位置的右边界。
状态转移方程:R[i] = R[R[i] + 1];
最近非常喜欢开输入挂。。
另外,这是单调栈的练手题。。也来了一发。。
dp实现:
#include <cstdio> #include <algorithm> using std::max; const int MAXN = 100000 + 10; int n; int h[MAXN]; int L[MAXN], R[MAXN]; int ReadInt() { int ret = 0; char ch; while ((ch = getchar()) && ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; } return ret; } void Read() { getchar(); for (int i = 1; i <= n; ++i) { h[i] = ReadInt(); } } void Dp() { long long ret = 0; for (int i = 1; i <= n; ++i) { L[i] = i; while (L[i] - 1 >= 1 && h[L[i] - 1] >= h[i]) { L[i] = L[L[i] - 1]; } } for (int i = n; i >= 1; --i) { R[i] = i; while (R[i] + 1 <= n && h[R[i] + 1] >= h[i]) { R[i] = R[R[i] + 1]; } } for (int i = 1; i <= n; ++i) { ret = max(ret, (long long)(R[i] - L[i] + 1) * h[i]); } printf("%I64d\n", ret); } int main() { while (scanf("%d", &n) == 1 && n) { Read(); Dp(); } return 0; }
单调栈实现:
#include <cstdio> #include <algorithm> using std::max; const int MAXN = 100000 + 10; struct MS { int st[MAXN]; int top; MS(): top(0) {} void Init() { top = 0; } void PushMin(int* A, int i) { while (top != 0 && A[i] <= A[st[top - 1]]) { --top; } st[top++] = i; } int Size() { return top; } int Second() { return st[top - 2]; } }; int n; int h[MAXN]; int L[MAXN], R[MAXN]; int ReadInt() { int ret = 0; char ch; while ((ch = getchar()) && ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; } return ret; } void Read() { getchar(); for (int i = 1; i <= n; ++i) { h[i] = ReadInt(); } } void Solve() { long long ret = 0; MS ms; for (int i = 1; i <= n; ++i) { ms.PushMin(h, i); if (ms.Size() == 1) { L[i] = 1; } else { L[i] = ms.Second() + 1; } } ms.Init(); for (int i = n; i >= 1; --i) { ms.PushMin(h, i); if (ms.Size() == 1) { R[i] = n; } else { R[i] = ms.Second() - 1; } } for (int i = 1; i <= n; ++i) { ret = max(ret, (long long)(R[i] - L[i] + 1) * h[i]); } printf("%I64d\n", ret); } int main() { while (scanf("%d", &n) == 1 && n) { Read(); Solve(); } return 0; }