84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

class Solution {
public:

    void cal(vector<int>& heights, vector<int>& dp)
    {
        dp.push_back(-1);
        for(int i = 1; i < heights.size(); i++)
        {
            if(heights[i] > heights[i - 1])
                dp.push_back(i - 1);
            else
            {
                int k = dp[i - 1];
                while(k != -1 && heights[i] <= heights[k])
                {
                    k = dp[k];
                }
                dp.push_back(k);

            }
        }
    }

    int largestRectangleArea(vector<int>& heights) {
        vector<int> heightscopy;
        for(int i = heights.size() - 1; i >= 0; i--)
        {
            heightscopy.push_back(heights[i]);
        }
        vector<int> dp1, dp2;
        cal(heights, dp1);
        cal(heightscopy, dp2);
        int ret = 0, n = heights.size();
        for(int i = 0; i < n; i++)
        {
            ret = max(ret, heights[i] * (i - dp1[i] + n - i - 1 - dp2[n - i - 1] - 1));
        }

        return ret;



    }
};