原题地址
https://leetcode.com/problems/largest-rectangle-in-histogram/description/
题意
给出一个vector<int>表示直方图，找出直方图里最大的矩形，返回其面积。
代码
一开始用了最粗暴的O（N^2）的解法
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int col = heights.size();
if (col == 0) return 0;
int area = 0;
vector<vector<long> > dp(col, vector<long>(col, 0));
for (int i = 0; i < col; i++) {
int lowest = heights[i];
for (int j = 0; j <= i; j++) {
if(heights[i-j]<lowest){
lowest=heights[i-j];
}
dp[i][j]=lowest*(j+1);
if(dp[i][j]>area){
area=dp[i][j];
}
}
}
return area;
}
};
果然超时了
