signed

QiShunwang

“诚信为本、客户至上”

构造建筑的最高高度

2021/4/26 16:30:06   来源:

LINK

有n=1e9栋建筑,编号是[1, 2, ..., n]1栋建筑的高度固定为[0]' 相邻两栋建筑的高度差 <= 1 '
比如:[0, 1, 2, 3, 4, 4, 4, 4] 就是一种合法方案

现给定你一个limit的pair类型数组
{a, b}表示:  a编号的建筑,最高不可以超过b高度
 且limit中: 不会有重复的编号a, 不会有a=1(因为1建筑高度固定了)
' 求, 这n栋建筑中的最大值  最高是多少 '
   (即,你无需关注这n栋建筑的排布, 只需关注最高可以达到多少即可)

比如n = 6,  limit=[ {6,1} ]
 虽然理想是:[0, 1, 2, 3, 4, 5],但由于6号建筑需要<=1
 [0, 1, 2, 3, 2, 1]    即ans = 3
 

1, 假如说limit为空, 即没有限制
   就真的没有限制了吗??? 
   其实依然是有限制的!!!
   (1号建筑的高度 == 0) (相邻建筑的高度差 <= 1)
   此时: ans = n-10, 1, 2, 3, ... 】是最优
   ' 也就是: 即便limit数组是空, 你依然可以得到: '
   '			H[i] <= (i - 1) 这个限制!! ' 
   我们用H[i]表示:  i建筑的最高高度
   我们从H[1]==0, 就可以得到:
      H[i] <= (0 + i)

比如,对于某个建筑 H[i] <= k
 则' 他影响的,不仅是i这个建筑!! 他会影响所有的建筑!! '
 仅仅根据H[i] <= k 这个性质, 你可以得到:
     H[i-1] <= (k+1)     H[i+1] <= (k+1)
     H[i-2] <= (k+2)     H[i+2] <= (k+2)
     H[i-3] <= (k+3)     H[i+3] <= (k+3)
	 通式:     H[i +- j] <= (k + j)
  ' 这个是非常非常重要的,  思路一定要打开 '
  '  一定要理解,H[]数组的定义!! 他表示的是: 最大的合法 '
  ' 你肯定会想:  比如 H[3] <= 5 '
  '   则会推导出: H[2/4] <= 6。 '
  '   但如果说, H[3]不是取5, 比如3号建筑最终取的高度是2 '
  '   那么, 应该是: H[2/4] <= (2+1) !! '
  那么, 我们推导出的 H[2/4] <= (5+1) 是否是错的呢??? 
   所以说, 得到H[2/4] <= (5+1)这个式子,是非常不易的 也是非常核心的思路
    这个H[]数组,他表示的 '并不是说,这个元素实际的取值!!!'
     
2