少年听雨歌楼上
红烛昏罗帐
直接上代码了就。。。
首先是暴力的版本，基本思路和下雨填那个水坑一样的。。会超时！！！
class Solution {
private:
int getEdge(int start, int step, vector<int>& hs) {
int temp = hs[start];
int ans = start;
while (start >= 0 && start < hs.size() && hs[start] >= temp) {
ans = start;
start += step;
}
return ans;
}
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
int ans = 0;
for (int i = 0; i < n; i++) {
int left = getEdge(i, -1, heights);
int right = getEdge(i, 1, heights);
ans = max(ans, heights[i] * (right - left + 1));
}
return ans;
}
};
然后就是使用单调栈：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
stack<int> s1, s2;
vector<int> hash1(n), hash2(n);
for (int i = 0; i < heights.size(); i++) {
while (!s1.empty() && heights[s1.top()] >= heights[i])
s1.pop();
if (s1.empty()) hash1[i] = 0;
else hash1[i] = s1.top() + 1;
s1.push(i);
}
for (int i = n - 1; i >= 0; i--) {
while (!s2.empty() && heights[s2.top()] >= heights[i])
s2.pop();
if (s2.empty()) hash2[i] = n - 1;
else hash2[i] = s2.top() - 1;
s2.push(i);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, heights[i] * (hash2[i] - hash1[i] + 1));
}
return ans;
}
};
