LeetCode开心刷题三十四天——84. Largest Rectangle in Histogram

喜欢ヅ旅行 2023-08-17 15:14 78阅读 0赞

84. Largest Rectangle in Histogram

Hard

215858FavoriteShare

Given *n* non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

![histogram.png][]  
Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

![histogram_area.png][]  
The largest rectangle is shown in the shaded area, which has area = `10` unit.

Example:

Input: [2,1,5,6,2,3]
    Output: 10

This problem is a bold attempt(大胆尝试) for me ,because I try multiply ways to solve this problem.I've been heard multi-way can make people get clear

左右遍历法：

1.O(n) 左右遍历

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<map>
    #include<algorithm>
    #include<stack>
    #include<climits>
    //
    using namespace std;
    class Solution
    {
    public:
        int largestRectangleArea(vector<int>& height)
        {
            //NULL
            if(height.empty()) return 0;
            //Judge
            int n=height.size();
            //store
            int *left=new int[n];
            int *right=new int[n];
            int maxArea=0;
            //left
            left[0]=1;
            for(int i=1;i<n;i++)
            {
                if(height[i]>height[i-1])
                {
                    left[i]=1;
                }
                else
                {
                    int j=i-1;
    　　　　　　　　　　//always easy miss =
                    while(j>=0&&height[j]>=height[i])
                    {
                        j-=left[j];
                    }
                    left[i]=i-j;
                    //cout<<"i"<<left[i]<<endl;
                }
            }
            //right
            right[n-1]=1;
            for(int i=n-2;i>=0;i--)
            {
                if(height[i]>height[i+1])
                {
                    right[i]=1;
                }
                else
                {
                    int j=i+1;
                    while(j<n&&height[j]>=height[i])
                    {
                        j+=right[j];
                    }
                    right[i]=j-i;
                }
            }
            //MaxArea
            for(int i=0;i<n;i++)
            {
                //former problem cannot use right+left,1.left is not abs 2.i is not 0
                maxArea=max(maxArea,(right[i]-left[i]+1)*height[i]);
                cout<<"r"<<right[i]<<"l"<<left[i]<<endl;
                cout<<"M"<<maxArea<<endl;
            }
            return maxArea;
        }
    };
    int main()
    {
        vector<int> res={
         1,1};
        Solution s;
        cout<<s.largestRectangleArea(res)<<endl;
        return 0;
    }

2.O(n^2)

省代码但是耗时

单调栈：

C++：

class Solution {
    public:
        int largestRectangleArea(vector<int> &height) {
            int res = 0;
            for (int i = 0; i < height.size(); ++i) {
                if (i + 1 < height.size() && height[i] <= height[i + 1]) {
                    continue;
                }
                int minH = height[i];
                for (int j = i; j >= 0; --j) {
                    minH = min(minH, height[j]);
                    int area = minH * (i - j + 1);
                    res = max(res, area);
                }
            }
            return res;
        }
    };

python：

class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            # store
            stack = list()
            res = 0
            heights.append(0)
            # judge
            N = len(heights)
            for i in range(N):
                if not stack or heights[i] > heights[stack[-1]]:
                    stack.append(i)
                else:
                    while stack and heights[i] <= heights[stack[-1]]:
                        h = heights[stack[-1]]
                        # pop to find boundary
                        stack.pop()
                        # special minus distance i distance+1 stack[-1] distance-1
                        w = i if not stack else i - stack[-1] - 1
                        res = max(res, h * w)
                    # this step easy forget.i isn't former calculation.Need to push stack
                    stack.append(i)
            return res
    
    solu=Solution()
    # 赋值输出一条龙
    print(solu.largestRectangleArea(heights=[2,1,5,6,2,3]))

转载于:https://www.cnblogs.com/Marigolci/p/11347210.html

[histogram.png]: https://assets.leetcode.com/uploads/2018/10/12/histogram.png
[histogram_area.png]: https://assets.leetcode.com/uploads/2018/10/12/histogram_area.png