LeetCode 84. 柱状图中最大的矩形、85. 最大矩形（单调栈2）

1. 单调栈作用：在一维数组中找第一个满足某种条件的数
2. 将题目转换为，找到heights[i]左右第一个比heights[i]小的下标[left，right]
3. 下一个更小元素==>递增栈

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

两次循环，利用单调栈填表vector left,right

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        int ans=0;
        stack st;
        int n=heights.size();
        vector left(n,-1),right(n,n);
        //找右边界
        for(int i=0;i
            while(!st.empty()&&heights[i]
                int tmp=st.top();
                st.pop();
                right[tmp]=i;
            }
            st.push(i);
        }
        st=stack();
        //找左边界
        for(int i=n-1;i>=0;i--){
            while(!st.empty()&&heights[i]
                int tmp=st.top();
                st.pop();
                left[tmp]=i;
            }
            st.push(i);
        }
        for(int i=0;i
            ans=max(ans,(right[i]-left[i]-1)*heights[i]);
        }
        return ans;
    }
};

对解一进行优化，一次循环。出栈找right(i)，入栈找left(stk.top())

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        int ans=0;
        stack st;
        int n=heights.size();
        vector left(n,-1),right(n,n);
        for(int i=0;i
            while(!st.empty()&&heights[i]
                //出栈时找到right(right=i),right是可信的
                int tmp=st.top();
                st.pop();
                right[tmp]=i;
            }
            //入栈时找到left,此时栈顶元素>=height[i],相同元素最左边的left是可信的
            if(!st.empty()){
                left[i]=st.top();
            }
            st.push(i);
        }
        for(int i=0;i
            ans=max(ans,(right[i]-left[i]-1)*heights[i]);
        }
        return ans;
    }
};

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

dp求出每个点的leftMax，作为左边最大’1’的个数的条形统计图。
对同列的元素分别求柱状图中最大的矩形（84）

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector> left(m,vector(n,0));
        for(int i=0;i
            for(int j=0;j
                if(j==0||matrix[i][j]=='0'){
                    left[i][j]=matrix[i][j]-'0';
                }else{
                    left[i][j]=left[i][j-1]+1;
                }
            }
        }
        int ans=0;
        for(int j=0;j
            stack st;
            vector l(m,-1),r(m,m);
            for(int i=0;i
                while(!st.empty()&&left[i][j]
                    int tmp=st.top();
                    st.pop();
                    r[tmp]=i;
                }
                if(!st.empty()){
                    l[i]=st.top();
                }
                st.push(i);
            }
            for(int i=0;i
                ans=max(ans,(r[i]-l[i]-1)*left[i][j]);
            }
        }
        return ans;
    }
};