牛客算法-第一章

1. 给定一个 N*2 的二维数组,看作是一个个二元组,例如[[a1,b1],[a2,b2],[a3,b3]],
规定:一个如果想把二元组甲放在二元组乙上,甲中的 a 值必须大于乙中的 a 值,甲中的 b
值必须大于乙中的 b 值。如果在二维数组中随意选择二元组,请问二元组最多可以往上摞
几个?
例如:[[5,4],[6,4],[6,7],[2,3]], 最大数量可以摞 3 个,[2,3] => [5,4] => [6,7]
要求:实现时间复杂度 O(N*logN)的解法

总结:算法原型是求解数组中最长递增子序列。

如:arr数组
 2 3 5 1 6 7 4

首先,如何求解数组中最长递增子序列呢?
两种方法,O(N^2)和O(N logN)
1.dp数组,用dp[i]记录以arr[i]结尾的最长子序列长度;
2.需要用到二分,遍历过程是N,插入过程是logN,核心思想是:h数组,h[i]记录以arr[i]结尾的最长子序列的最小末尾的值。

上面左神的求解使用数组,如果用c++中的stl中vector直接记录,然后最后直接v1.length()就是最长递增子序列的长度。
而for(auto x:v1),也可以将最长递增子序列的结果遍历显示。

以上就是对算法原型的归纳,下面回归原题的算法求解。

题目给定的是一个二元组,也就是比较的对象变为了两个(a,b)。如果设置比较器,是一个关键的步骤。

(1,10)| (2,15) | (3,12)
 ...       ...        ...
(1,1) | (2,3)  | (3,2)

以上排序的步骤是如何设计的呢?
假设存在A(a,b),B(a,b)
那么先进行 A.a<B.a ,也就是对a升序排列;然后进行A.b>B.b,也就是对b降序排列。

这里是一个排列的技巧,因为这样排列,的话,我们引用上面的算法原型,就可以在数组h中只记录,最长子序列的最小末尾b,也就是数组h也是一个一维数组就可以。
而且,这样做规避了比较过程的一个冲突,例如:
(3,10000),(4,5)两者的比较。

之后的话,就是同样的操作,具体不再详述。




2.给定一个非负数的数组,代表一个容器。例如数组[0,1,0,2,1,0,1,3,2,1,2,1],就是
以下图形中黑色的部分。如果用这个容器接水的话,请问可以接多少水?还以这个数组为例,
可以接 6 格水,就是以下图形中蓝色的部分。
要求:实现时间复杂度 O(N),额外空间复杂度 O(1)的解法

总结:这道题的想法比较多。其中还提到,程序员应具有简化业务的能力。以下记录算法思想。

1.遍历数组arr,找到max(arr.begin(),arr.end()),也就是找到最大值。
然后从最大值max开始,从左遍历找左边部分的最大值lmax,从右遍历找右边部分的最大值rmax。
所以基于此处最大值的左右水池,就是左边lmax到max的位置,加上max到右边rmax的位置,两者共同积累的水,接下来就是在从lmax遍历其左边,rmax遍历其右边。。。

2.第二种方法,简化模型,如果已知arr数组中i下标的值为5,即arr[i]=5;那么我们的思想变为求解此处坐标处积累的水量,就是他头上那部分。
那么如何求解呢?举例,如果其lmax=10,rmax=20,那么该坐标处积累的水量呢?很明显是10-5=5;已知了i处的水量,那么所有的水量呢?加起来就可以得出了。
方程很明显就是
max(0,( min(max(0...i-1),max(i+1,n-1) ) -arr[i] )  )

注意,最外层的max是为了保证水量不可能是负数。

接下来就是对于解决方案的具体讨论,针对每次遍历到某一点i下标处,我们都要循环遍历其左右两边求解lmax以及rmax,我们可以有改进方案,就是设置lmax数组和rmax数组。

lmax数组就是从0~n-1遍历,lmax[i],就是从0到i的序列中的最大值。
对应的,rmax数组就是从n-1~0倒序遍历,rmax[i],就是从n-1到i的序列中的最大值。

注意,此处左神还给出了一点,就是其实我们只需要有rmax数组,因为我们的求解顺序是从左到右的,在这个过程中,可以用个变量max就实时记录i处的左边序列的最大值了。

回归这道题,需要不用额外空间,如何解决呢?

举例 :

	    5 4 6 ...     3  7
	    |                |
	    L                R


以上是最初状态,然后我们还需要一个lmax变量,和rmax变量。
该开始,左右开始滑动l和r,
当r已经是7的时候,也就是rmax最小也是7了,也就是右边的最大值一定比左边的最大值5大,所以我们选5,因为我们是选得最小值,没有必要去移动r,然后lmax=5,记录下来,此时4的水量已经可以结算了。l向右移动,我们判断6,同样的处理。
总结就是那一侧结算,哪一侧的游标就向右滑。






3.给定一个非负数的数组,数组中的每个值代表一个柱子的高度,柱子的宽度是 1。两个柱
子之间可以围成一个面积,规定:面积=两根柱子的最小值*两根柱子之间的距离。比如数
组[3,4,2,5]。3 和 4 之间围成的面积为 0,因为两个柱子是相邻的,中间没有距离。3 和
2 之间围成的面积为 2,因为两个柱子的距离为 1,且 2 是最短的柱子,所以面积=1*2。
3 和 5 之间围成的面积为 6,因为两个柱子的距离为 2,且 3 是最短的柱子,所以面积=
3*2。求在一个数组中,哪两个柱子围成的面积最大,并返回值。
要求:实现时间复杂度 O(N),额外空间复杂度 O(1)的解法

关键点:移动的方法不会错过最优的结果,就是潜在的最大的那个结果就行。全局量max进行保存。

举例 : 6… 7
中间举例为 10,
现在我们如何移动,移动 L ,还是移动 R,才不会错过最优解呢?
很简单,6<7,所以,我们哪个小动哪个,所以移动 L 游标。

关键点,还是一个双端指针的问题,two points.