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;
    }
};