直方图下最大面积矩形

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

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

我们先想想左边面积怎么求。如果给你一段单调增的序列,比如 1,2,3,4… 那么每个最左边的面积很自然为 0,但是如果是单调减的,比如 5,4,3,2,1,那么我们就可以尝试去掉前面的,但是记个数在那里,这样就不会导致每次要向前数数(这样就变成 O(N^2) 了)。去掉前面的也有问题,因为前面的除非左右面积都算出来了,否则就无法完成前面的需求。为了解决这个问题,我们需要用一个 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:

Advertisements
直方图下最大面积矩形

一个有关“直方图下最大面积矩形”的想法

  1. Lianghao 说:

    用stack的trick比较大比较难想。可以考虑双向DP,用L和R分别记录当前bar的最左最右边界,时间复杂度是O(n),然后在O(n)扫描一遍算出最大即可。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s