题目

• 题目链接

思考

方法1: O(n^2)的遍历做法.

• 很简单, 一个个rectangle area计算出来, 然后枚举/排序/找最大.
• 这里outer loop来抓每一个area的height, 然后分别从它向左/右找第一个比他小的数. 然后计算面积. 在计算的过程中update ans.
• 这里向左向右的while loop找lhs/rhs可以追述到Algs4的Binary search, Quick Sort的partition. 或者是Maximum subarray的Divide & Conquer的做法.
• 这里很重要的一点: 还是: 数列问题的index. 这里的终止条件是i = -1 || i = length. 这样的话, 可以统一起来lhs总是比他小的那个位置, rhs总是比他大的那个位置. 从而width = rhs-lhs-1.

方法2: Stack的使用: O(1)找左右第一个比他小的数

• Stack又一个用法: 一个严格单调递增的stack. 它的左边第一个就是就是比它小的第一个数.

• 九章课上说, 可以有2个方法:

  1. 正着跑一边incStk, 找到他的左边第一个比他小的位置, 然后reverse array, 再跑一遍stack, 找到右边第一个比他小的位置. (这和方法1有什么区别? 有的, 这个是O(n)找到所有点的左右范围.)
  2. 也可以是九章答案的做法, 就是for里面一个while, 来维持单调递增性, 若违反了, 则说明找到了右边界, 因为其左侧第一个就是第一个比他小的数的位置.

• 但是: 虽然意思懂了, 但是一做发现很多错误! 我第一次在Lintcode上面写就出现了一个很好的错误: 如果[1,1]的话怎么弄? 应该输出2, 但我得到1! 这是因为我的width计算不对.

  • 有个很重要的点: 例如[1], 然后cur = 0. 那么右边界找到了, 接着pop, 于是incStk = []. 那么左边界是多少呢? 我当时直接i-l-1. 其中l是incStk.peek(). 其实这样不对. 也导致了我的area是1. 因为stack为空, 说明height[pop()]的左边界是通到i = 0! 即width = i.
  • 上面的这个错误的原因还有一个! 就是我在while loop判断的时候用的是”<”, 也就是维护的是一个单调不递减stack, 而不是单调递增stack. 这样的后果是, incStk出现了[1,1], 然后cur = 0. 接着pop位于第二个的1. 算出来的不知道是有什么物理意义. 所以正确的做法是while loop的判断用的是<=. 从而保证单调递增, 即左边就是比它小的数.

方法3: Dynamic programming: 凡是找极值都应该想想动态规划.