84. 柱状图中最大的矩形

标签：pre int heights 柱状图 vector 84 矩形 dp

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

      解析： 话说我删了一个没必要的if，为啥时间增加了，无语子。 其实很简单，对每个i，求其左右两边第一个小于当前heights[i]的下标即可 左右两边分开单独求 这里只看左边 dp[i]表示小于heights[i]的下标 如果heights[i - 1] < heights[i]， 则 dp[i] = i - 1; 否则 令k = dp[i - 1]，重复k = dp[k]，直到k = -1 或者 heights[k] < heights[i] 证明：为什么最终的k可以？ 设pre为上一个k，那么最后一个k和pre之间没有符合的值吗 答案是没有 因为heights[pre] >= heights[i]，（否则k就等于pre了） 所以如果存在kk，使得heights[kk] >= heights[k] 且 heights[kk] < heights[i] 那么dp[pre] 就等于kk了，而不是k了，矛盾 得证

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;



    }
};

 

标签：pre,int,heights,柱状图,vector,84,矩形,dp
From： https://www.cnblogs.com/WTSRUVF/p/16622915.html