Largest Rectangle in Histogram（C++柱状图中最大的矩形）

梦里梦外; 2023-01-17 03:16 111阅读 0赞

（1）遍历（超时）

class Solution {
    public:
        int largestRectangleArea(vector<int>& h) {
            int n=h.size(),len=0;
            vector<int> v(n,0);
            for(int i=0;i<n;i++) {
                len=0;
                for(int j=0;j<n;j++) {
                    if(h[j]>=h[i]) len++;
                    else {
                        v[i]=max(v[i],len);
                        len=0;
                    }
                    v[i]=max(v[i],len);
                }
            }
            
            int maxsum=0;
            for(int i=0;i<n;i++) {
                maxsum=max(maxsum,h[i]*v[i]);
            }
            return maxsum;
        }
    };

（2）单调栈

class Solution {
    public:
        int largestRectangleArea(vector<int>& h) {
            int n=h.size();
            vector<int> left(n),right(n,n);
            
            stack<int> s;
            for(int i=0;i<n;i++) {
                while(!s.empty() && h[s.top()]>=h[i]) {
                    right[s.top()]=i;
                    s.pop();
                }
                left[i]=s.empty()?-1:s.top();
                s.push(i);
            }
            
            int maxsum=0;
            for(int i=0;i<n;i++) {
                maxsum=max(maxsum,(right[i]-left[i]-1)*h[i]);
            }
            return maxsum;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，111人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode84:柱形图中最大的矩形(Largest Rectangle in Histogram)

英文题目： Given n non-negative integers representing the histogram’s bar height where t...

雨点打透心脏的1/2处/ 2024年04月19日 08:03/ 0 赞/ 70 阅读

相关 leetcode:84. 柱状图中最大的矩形

题目: 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。以上是柱状图的示例，

快来打我*/ 2023年06月25日 04:38/ 0 赞/ 21 阅读

相关（Java）leetcode-84 Largest Rectangle in Histogram（柱状图中最大的矩形）

题目描述难度：hard 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

Myth丶恋晨/ 2023年03月01日 09:22/ 0 赞/ 5 阅读

相关柱状图中最大的矩形(Largest Rectangle in Histogram)——单调栈经典题目

柱状图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。 ![在

小灰灰/ 2023年02月14日 02:04/ 0 赞/ 8 阅读

相关柱状图中最大的矩形多种解法

一、前言问题来源LeetCode 84，难度：困难问题链接：[https://leetcode-cn.com/problems/largest-rectangle-

痛定思痛。/ 2023年02月11日 12:28/ 0 赞/ 10 阅读

相关 Largest Rectangle in Histogram（C++柱状图中最大的矩形）

（1）遍历（超时） class Solution { public: int largestRectangleArea(vector<int>

梦里梦外;/ 2023年01月17日 03:16/ 0 赞/ 112 阅读

相关【LeetCode】柱状图中最大的矩形、最大矩形（神之转化）

【LeetCode】柱状图中最大的矩形、最大矩形柱状图中最大的矩形★★★ [LeetCode84. 柱状图中最大的矩形][LeetCode84.] 【题目】给定

梦里梦外;/ 2023年01月05日 05:13/ 0 赞/ 147 阅读

相关 leetcode84柱状图中最大的矩形

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

小灰灰/ 2022年10月06日 06:52/ 0 赞/ 225 阅读

相关 LeetCode 柱状图中最大的矩形

1 柱状图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例

绝地灬酷狼/ 2022年09月14日 00:26/ 0 赞/ 194 阅读

相关 leetcode 84. Largest Rectangle in Histogram | 84. 柱状图中最大的矩形（单调栈）

题目 [https://leetcode.com/problems/largest-rectangle-in-histogram/][https_leetcode.com

深碍√TFBOYSˉ_/ 2022年09月11日 09:21/ 0 赞/ 196 阅读