解法一：
解题思路：
- 这题的基本思想是找出每一个矩形的左右边界（即左右边第一个比他高的），但如果直接对每一个矩形暴搜会超时。
- 于是可以dp一下：如果它原有左边界的左边第一个，比他本身还要高，那么它原有左边界的左边第一个的左边界就是它的左边界。晕了吧~看代码：
tmp = i; //先把左边界设为自己 while(arr[i] <= arr[tmp-1] && tmp > 1) tmp = left[tmp-1];
右边界同理
- 还要注意一点，就是tmp > 1 这句一定不能缺，表示如果左边界到了最左边，那么就是它了。
Read full article from POJ 2559 Largest Rectangle in a Histogram - 白~ - 博客园
No comments:
Post a Comment