leetcode 84,85 柱状图中最大的矩形，最大矩形（单调栈）

题目描述：

**84：**给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

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

思路：

85题是84的基础，参考此处

还有此处

代码如下：

84:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res=0;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        vector<int>index;
        for(int i=0;i<heights.size();i++){
            while(!index.empty()&&heights[index.back()]>heights[i]){
                int cur=index.back();
                index.pop_back();
                int left=index.back()+1;
                int right=i-1;
                res=max(res,(right-left+1)*heights[cur]);
            }
            index.push_back(i);
        }
        return res;
    }
};
           

85:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0)  return 0;
        int res=0;
        int m=matrix.size(),n=matrix[0].size();
        vector<int>heights(n,0);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='0'){
                    heights[j]=0;
                }
                else{
                    heights[j]+=1;
                }
            }
            res=max(res,largestRectangleArea(heights));
        }
        return res;
    }
    int largestRectangleArea(vector<int>heights){
        int res=0;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        vector<int>index;
        for(int i=0;i<heights.size();i++){
            while(!index.empty()&&heights[index.back()]>heights[i]){
                int temp=index.back();
                index.pop_back();
                int left=index.back()+1;
                int right=i-1;
                res=max(res,(right-left+1)*heights[temp]);
            }
            index.push_back(i);
        }
        return res;
    }
};