单调栈分类、封装和总结

class CRangIndex
{
public:
  template<class _Pr>
  CRangIndex(int iVectorSize, _Pr CurIndexCmpStackTopIndex)
  {
    m_c = iVectorSize;
    m_vLeft.assign(m_c, -1);
    m_vRight.assign(m_c, m_c);
    stack<int> sta;
    for (int i = 0; i < m_c; i++)
    {
      while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top())))
      {
        m_vRight[sta.top()] = i;
        sta.pop();
      }
      if (sta.size())
      {
        m_vLeft[i] = sta.top();
      }
      sta.emplace(i);
    }
  }
  template<class _Pr>
  CRangIndex(const vector<int>& nums, _Pr CurValueCmpStackTopValue)
  {
    m_c = nums.size();
    m_vLeft.assign(m_c, -1);
    m_vRight.assign(m_c, m_c);
    stack<int> sta;
    for (int i = 0; i < m_c; i++)
    {
      while (sta.size() && (CurValueCmpStackTopValue(nums[i], nums[sta.top()])))
      {
        m_vRight[sta.top()] = i;
        sta.pop();
      }
      if (sta.size())
      {
        m_vLeft[i] = sta.top();
      }
      sta.emplace(i);
    }
  }
  int m_c;
  vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};

int main()
{
  vector<int> nums;
  {
    nums = { 1,2,3,3,4 };
    CRangIndex ri(nums, std::less_equal<>());
    std::cout << "数组值：";
    CConsole::Out(nums);
    std::cout << "左边界：";
    CConsole::Out(ri.m_vLeft);
    std::cout << "左边界：";
    CConsole::Out(ri.m_vRight);
  }
  {
    nums = { 8,7,3,4 };
    CRangIndex ri(nums, std::less_equal<>());
    std::cout << "数组值：";
    CConsole::Out(nums);
    std::cout << "左边界：";
    CConsole::Out(ri.m_vLeft);
    std::cout << "左边界：";
    CConsole::Out(ri.m_vRight);
  }
}