直方图下最大面积矩形

这算是一个经典题目了，每次都没写出来 code，这次决定自己动个手。看了一些说法，其实感觉都没说清楚，自己尝试了半天之后终于搞清楚了这个 trick 的核心想法。

比较 naive 的做法大概是搜索所有的开始结束，因为其中最小值可以 incremental 更新，所以这个最大面积是一个 的操作，没啥问题。trick 是可以将这个操作降低到 的。核心的想法就是 第 i 个 bar 存在的时候的最大矩形面积，这个面积其实包括这个 bar 左边的面积（不包括自己），和右面的面积。那么怎么有效的计算出来这两个面积就成了关键问题。其实也很简单，左边找到比它小的下标最大的，右边找到比他小的下标最小的就行了。说起来容易，还是不知道怎么设计算法呢！

我们先想想左边面积怎么求。如果给你一段单调增的序列，比如 1,2,3,4… 那么每个最左边的面积很自然为 0,但是如果是单调减的，比如 5,4,3,2,1，那么我们就可以尝试去掉前面的，但是记个数在那里，这样就不会导致每次要向前数数（这样就变成 了）。去掉前面的也有问题，因为前面的除非左右面积都算出来了，否则就无法完成前面的需求。为了解决这个问题，我们需要用一个 stack，这个里面一开始存放  (0, 0, 0)，三个位置分别表示下标，值和左面积，我们可以看出来前面的要求需要两点：

• 入栈，当且仅当栈顶元素值没当前的大
• 入栈元素的左面积就是栈顶元素下标 + 1 到元素部分的面积，因为中间比该元素大的已经不在栈内了，这时计算出来左面积就可以跟该元素入栈了
• 如果栈顶元素比当前准备入栈的元素值大，那就得拿掉它，拿掉它时它在栈内了，左面积已经计算出来，所以出栈扔掉钱前我们得算出来右面积
• 因为待入栈元素比栈顶元素值小，所以右边的矩形最多到待入栈元素下标 -1，可不可能不满足高度约束呢？不可能，否则还没到当前元素入栈，就会导致栈顶元素出栈了

这样站内元素的高度是单调增的，如果处理完所有数据后站内还有元素，直接出栈剩余的即可，右面积很容易算出来（长度是数组长度减去下标）。ok 废话不多说，上 code，C++11 下编译通过。

template <class T> T
max_rect_under_hist (const std::vector<T>& h) {
  std::stack<std::tuple<int, T, T> > s ;
  T max_area = 0, cur_area ; s.push (std::make_tuple(0, 0, 0)) ;

  for (int i = 0 ; i < h.size () ; ++ i) {
    T left_area = 0 ;
    if (h[i] < std::get<1> (s.top ())) {
      while (h[i] < std::get<1> (s.top ())) {
        // right area + left area
        cur_area = (i - std::get<0> (s.top ()) + 1) * std::get<1> (s.top ())
          + std::get<2> (s.top ()) ;
        max_area = std::max (cur_area, max_area) ;
        s.pop () ;
      }
      // left area
      left_area = h[i] * (i - std::get<0>(s.top ())) ;
    }

    // push the current one onto the stack
    s.push (std::make_tuple (i+1, h[i], left_area)) ;
  }
  // check those left on the stack
  while (s.size () > 1) {
    cur_area = std::get<1> (s.top ()) * (h.size () - std::get<0> (s.top ()) + 1)
      + std::get<2> (s.top ()) ;
    max_area = std::max (cur_area, max_area) ;
    s.pop () ;
  }
  return max_area ;
}

似乎有人喜欢说用 backtrack 来解，其实我不是太明白这个思路和 backtrack 的关系，望达人明示！

——————
And these are the generations of Isaac, Abraham’s son: Abraham begat Isaac: