还未完成 Leetcode 84. Largest Rectan

原题地址

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;
    }
};

果然超时了