原本并没有重视这个技巧,但是后来回过头再来做几道关于DP的题目,意外地发现这个做法可以将O(n^2)的复杂度优化至O(n)!所以打算将这类题目做一个总结吧。


直方图最大矩形覆盖

Description

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example, given height = [2,1,5,6,2,3].

阅读全文 »