先附上几个链接和相关题目，写的都非常的好：
https://discuss.leetcode.com/topic/1634/a-o-n-2-solution-based-on-largest-rectangle-in-histogram
https://discuss.leetcode.com/topic/6650/share-my-dp-solution
https://leetcode.com/problems/largest-rectangle-in-histogram/#/description
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0Return 6.
求矩阵中最大的全1矩阵。
思路：
把求最大全1矩阵转换成求最大直方图面积，如下转换：
1 0 1 0 0 2 0 2 1 1 3 1 3 2 2 4 0 0 3 0 这样就可以对每一行遍历，求这一行的最大直方图了。 那么要求最大的直方图，不是特别容易。例如3 1 3 2 2这一行，我们可以发现，如果3后面出现了比3小的数，那么以这个数为终点的直方图其实和3没什么关系，这个直方图的大小直到和3前面比他小的那个数才有关系。 假如这个序列式3 4 3 2 2，那么3后面是4，以4为终点的直方图就他前面的3有关系了。所以我们要维护一个单调上升的一个序列。从前往后扫描，如果碰到的数比序列最后一个数要大，那么这个以这个位置为终点的直方图和前面的所有位置都有关，这时候直接把这个数加进序列最后就可以了。如果碰到的数比序列中最后一个数小，就依次弹出序列中比这个数大的数，并且压进与弹出数的个数同样的当前数字。注意当弹出大的数的时候，我们是需要计算以这个大的数为终点的直方图的大小的。 class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { if (matrix.size() == 0) { return 0; } vector<vector<int>> height(matrix.size(), vector<int>(matrix[0].size(),0)); for (int i = 0; i < matrix[0].size(); i++) { if (matrix[0][i] == '1') { height[0][i] = 1; } else { height[0][i] = 0; } } for (int i = 1; i < matrix.size(); i++) { for (int j = 0; j < matrix[0].size(); j++) { if (matrix[i][j] == '1') { height[i][j] = height[i-1][j] + 1; } else { height[i][j] = 0; } } } int ans = 0; for (int i = 0; i < matrix.size(); i++) { stack<int> st; for (int j = 0; j < matrix[0].size(); j++) { int u = 0; while (!st.empty() && st.top() > height[i][j]) { u++; ans = max(ans, u * st.top()); st.pop(); } while (u) { u--; st.push(height[i][j]); } st.push(height[i][j]); } int p = matrix[0].size(); while (!st.empty()) { int m = st.top() * (matrix[0].size() - p + 1); // cout << st.top() << " " << m << endl; ans = max(ans, m); p--; st.pop(); } } return ans; } }; 分治法：最大矩形面积只可能有三种情况： 1. 取决于高度最小的柱子，此时面积等于高度乘总长度； 2. 最大面积出现在高度最小的柱子左边； 3. 最大面积出现在高度最小的柱子右边； ''' n = int ( raw_input ()) h = [ int (x) for x in raw_input ().split()] def largestarea(a): l = len (a) idx = a.index( min (a)) value1 = a[idx] * l if idx ! = 0 : value2 = largestarea(a[ 0 :idx]) else : value2 = 0 if idx ! = l - 1 : value3 = largestarea(a[idx + 1 :l]) else : value3 = 0 return max (value1, value2, value3) print largestarea(h)