84. 柱状图中最大的矩形

2022/8/25 6:24:06

本文主要是介绍84. 柱状图中最大的矩形,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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;



    }
};

 



这篇关于84. 柱状图中最大的矩形的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程