【单调栈】【网格】【柱图面积】85. 最大矩形

}
int AddIndex(int cur)
{
  while (m_queIndexs.size() && (m_pr(m_nums[cur], m_nums[m_queIndexs.back()])))
  {
    m_queIndexs.pop_back();
  }
  int iRet = (m_queIndexs.size()) ? m_queIndexs.back() : -1;
  m_queIndexs.push_back(cur);
  return iRet;
}
void RemoveHeadIndex(int cur)
{
  if (m_queIndexs.size() && (cur == m_queIndexs.front()))
  {
    m_queIndexs.pop_front();
  }
}
const deque<int>& Que;

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<vector<char>> matrix;
  {
    Solution sln;
    matrix = { {'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'} };
    auto res = sln.maximalRectangle(matrix);
    Assert(6, res);
  }
  {
    Solution sln;
    matrix = { {'0'} };
    auto res = sln.maximalRectangle(matrix);
    Assert(0, res);
  }
  {
    Solution sln;
    matrix = { {'1'} };
    auto res = sln.maximalRectangle(matrix);
    Assert(1, res);
  }
}

template<class _PrCurValueCmpTailValue>
class CRangFeture
{
public:
  CRangFeture(const vector<int>& nums) :m_nums(nums), Que(m_queIndexs)
  {
  }
  int AddIndex(int cur)
  {
    while (m_queIndexs.size() && (m_pr(m_nums[cur], m_nums[m_queIndexs.back()])))
    {
      OnPop(cur, m_queIndexs.back());
      m_queIndexs.pop_back();
    }
    int iRet = (m_queIndexs.size()) ? m_queIndexs.back() : -1;
    m_queIndexs.push_back(cur);
    return iRet;
  }
  void RemoveHeadIndex(int cur)
  {
    if (m_queIndexs.size() && (cur == m_queIndexs.front()))
    {
      m_queIndexs.pop_front();
    }
  }
  const deque<int>& Que;
protected:
  virtual void OnPop(int cur, int pre) {};
  int FrontValue()
  {
    return m_nums[m_queIndexs.front()];
  }
  deque<int> m_queIndexs;
  const vector<int>& m_nums;
  _PrCurValueCmpTailValue m_pr;
};
template<class _PrCurValueCmpTailValue>
class CLeftRight : public CRangFeture<_PrCurValueCmpTailValue>
{
public:
  CLeftRight(const vector<int>& nums) :CRangFeture<_PrCurValueCmpTailValue>(nums)
  {
    m_vLeft.assign(nums.size(), -1);
    m_vRight.assign(nums.size(), nums.size());
  }
  void Init()
  {
    for (int i = 0; i < this->m_nums.size(); i++)
    {
      m_vLeft[i] = this->AddIndex(i);
    }
  }
  vector<int> m_vLeft, m_vRight;
protected:
  void OnPop(int cur, int pre)
  {
    m_vRight[pre] = cur;
  }
};
class Solution {
public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    m_c = matrix[0].size();
    vector<int> vHeight(m_c);
    int iRet = 0;
    for (int r = 0; r < matrix.size(); r++)
    {
      for (int c = 0; c < m_c; c++)
      {
        if (('0' == matrix[r][c]))
        {
          vHeight[c] = 0;
        }
        else
        {
          vHeight[c]++;
        }
      }
      iRet = max(iRet, MaxArea(vHeight));
    }
    return iRet;
  }
  int MaxArea(const vector<int>& vHeight)
  {   
    CLeftRight<std::less<int>> lr(vHeight); 
    lr.Init();
    int iRet = 0;   
    for (int i = 0; i < m_c; i++)
    {
      const int iArea = (lr.m_vRight[i] - lr.m_vLeft[i] - 1) * vHeight[i];
      iRet = max(iRet, iArea);
    }
    return iRet;
  }
  int m_c;
};