LeetCode OJ:Largest Rectangle in Histogram

Largest Rectangle in Histogram

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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cD48aW1nIHNyYz0="https://www.cppentry.com/upload_files/article/49/1_vydgf__.png" alt="\">

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

1、最初是用最大子矩阵求解，不过TLE

class Solution {
public:
    int largestRectangleArea(vector
  
    &height) {
        int len=height.size();
        vector
   
     L(len); vector
    
      R(len,len); vector
     
       sortH(height); sort(sortH.begin(),sortH.end()); int result=0; for(int i=0;i
      
       =sortH[i]){ L[j]=max(L[j],left); } else { left=j+1; L[j]=0;R[j]=len; } } for(int j=len-1;j>=0;j--){ if(height[j]>=sortH[i]){ R[j]=min(R[j],right); result=max(result,sortH[i]*(R[j]-L[j])); } else right=j; } } return result; } };
      
     
    
   
  

有个用栈实现的方法很好

struct node{
    int height;
    int index;
    node(int h,int i):height(h),index(i){}
};
class Solution {
public:
    int largestRectangleArea(vector
  
    &height) {
        if(height.empty())return 0;
        int len=height.size();
        int result=0;
        stack
   
     st; for(int i=0;i
    
     st.top().height){ st.push(node(height[i],i)); } else if(height[i]