leetcode84 柱状图

O(n^2) time 应用heights[r]<=heights[r+1]剪枝；

class Solution {

public:

    int largestRectangleArea(vector<int>& heights) {

        int n=heights.size();

        int res=0;

        for(int r=0;r<n;r++){

            if(r<n-1 && heights[r]<=heights[r+1]) continue;

            int h=heights[r];

            for(int l=r;l>=0;l--){

                if(heights[l]<h) h=heights[l];

                int cur_s=(r-l+1)*h;

                if(res<cur_s) res=cur_s;

            }

        }

        return res;

    }

};