【力扣练习记录】85.最大矩形

今天终于来做这题了
昨天写了84题,据说这题就是84的原理,一看,果然是,在84题的代码基础上外面套个for循环就解决了,仍然是用了单调栈哦

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].size();
        int ret=0;
        vector<vector<int>> heights(m,vector<int>(n));//一个二维数组
        for(int i=0;i<n;i++){
            heights[0][i]=matrix[0][i]-'0';
        }
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++){
            if(matrix[i][j]=='0'){
                heights[i][j]=0;
            }
            else{
                heights[i][j]=heights[i-1][j]+1;
            }
            }
        }

       for(int k=0;k<m;k++){
           stack<int>st;
        int newHeights[n+2];
        newHeights[0] = 0;
        newHeights[n+1] = 0;
        for (int i = 1; i < n+ 1; i++) {
            newHeights[i] = heights[k][i - 1];
        }

        // 开始遍历
        for (int i = 0;i<n+2; i++) {
            // 如果栈不为空且当前考察的元素值小于栈顶元素值,
            // 则表示以栈顶元素值为高的矩形面积可以确定
            while (!st.empty() && newHeights[i] < newHeights[st.top()]) {
                // 弹出栈顶元素
                int cur=st.top();
                st.pop();
                // 获取栈顶元素对应的高
                int curHeight = newHeights[cur];
                // 栈顶元素弹出后,新的栈顶元素就是其左侧边界
                int leftIndex = st.top();
                // 右侧边界是当前考察的索引
                int rightIndex = i;
                // 计算矩形宽度
                int curWidth = rightIndex - leftIndex - 1;
                ret =max(ret, curWidth * curHeight);
            }
            
            // 当前考察索引入栈
            st.push(i);
        }
       }

        return ret;
    }
};
上一篇:2019 第四周 开发笔记


下一篇:leetcode84.柱状图中最大的矩形