本文主要是介绍***Leetcode 85. Maximal Rectangle | 单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/maximal-rectangle/description/
当入栈的时候，求以入栈结点为右边界的最大的矩形， 当出栈的时候，求以出栈结点为做边界的最大矩形
最后需要一直把栈清空，检查栈里面是否还有合理解。
一个错误case是
2 3
如果不弹栈，得到答案是3，实际应该是4
class Solution {
public:int maximalRectangle(vector< vector<char> >& matrix) {if (!matrix.size() || !matrix[0].size()) return 0;vector< vector<int> > mat( matrix.size(), vector<int>(matrix[0].size(), 0) );int ans = 0;for (int i = 0; i < matrix.size(); i++) {vector< pair<int, int> > sta;for (int j = 0; j < matrix[0].size(); j++) {mat[i][j] = matrix[i][j] == '1';if (matrix[i][j] == '1' && i) {mat[i][j] += mat[i-1][j];}int idx = j;while (sta.size() && sta.back().first >= mat[i][j] ) {idx = min(idx, sta.back().second);// ans = max( ans, (j - idx ) * sta.back().first );ans = max( ans, (j - sta.back().second ) * sta.back().first );sta.pop_back();}sta.push_back( make_pair( mat[i][j] , idx) );ans = max( ans, (j - idx + 1 ) * mat[i][j] );} while (sta.size()) {ans = max(ans, ((int)matrix[0].size() - sta.back().second) * sta.back().first );sta.pop_back();}}return ans;}
};
这篇关于***Leetcode 85. Maximal Rectangle | 单调栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
