求水柱最大面积C++
时间: 2023-07-11 16:12:46 浏览: 34
以下是求水柱最大面积的C++代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
int getMaxArea(int hist[], int n) {
stack<int> s;
int max_area = 0;
int tp;
int area_with_top;
int i = 0;
while (i < n) {
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
else {
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
}
while (!s.empty()) {
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
int main() {
int hist[] = {6, 2, 5, 4, 5, 1, 6};
int n = sizeof(hist) / sizeof(hist[0]);
cout << "Maximum area is " << getMaxArea(hist, n);
return 0;
}
```
该算法基于单调递增栈的思想,时间复杂度为O(n)。