39）直方图最大矩形面积

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
      stack<int> s;
      int res=0;
      heights.push_back(0);
      for(int i=0; i<heights.size(); i++){
        while(!s.empty() && heights[s.top()]>=heights[i]){
          int h = heights[s.top()]; s.pop();
          if(s.empty()) res = max(res, h*i);
          else{
            res = max(res, h*(i-s.top()-1));
          }
        }
        s.push(i);
      }
      return res;
    }
};

40)矩阵中最大的矩形

class Solution {
public:
    int maximalRectangle(vector<string>& matrix) {
      if(matrix.empty()) return 0;
      vector<int> heights(matrix[0].size()+1);
      int res = 0;
      stack<int> s;
      heights.back() = -1;
      for(int i=0; i<matrix.size(); i++){
        for(int j=0; j<heights.size(); j++){
          if(j<heights.size()-1) heights[j] = matrix[i][j]=='1' ? heights[j]+1 : 0;
          while(!s.empty() && heights[s.top()]>=heights[j]){
            int h = heights[s.top()]; s.pop();
            if(s.empty()) res = max(res, h*j);
            else{
              res = max(res, h*(j-s.top()-1));
            }
          }
          s.push(j);
        }
        s.pop();
      }
      return res;
    }
};