阿里巴巴7.20笔试AK题解

第一题：重构数组

一开始看到想直接上链表了，但是想了一下其实直接每次交替着第最大的数字放到尾部和头部就是答案了。比如1 2 3 4，先把4放到尾部，然后把3放到头部，把2放到尾部，把1放到头部，最后答案就是3124。

第二题：石柱

相当于每回合会有两个操作，每回合至少产生一个0。然后朴素想法就是正着一点点合并区间。但是其实这道题逆向思维更好想。比如对于1 8 9 5 9 4这6根石柱，最后一个回合一定是9还大于0，而且1 8 5 4都变成0了。那么很明显两个9在这里将区间分成了5份，所以这时候有5根。然后到8，9肯定没你变成0，其他都变成0了。所以这时候6根。问题就是怎么维护区间了，方法很多，时候不早了，下次有空再来更新。

————更新————

首先我是用c++写的。我的做法是首先一开始合并一次，这是基操了。然后用一个新的数组b存下每个数的（大小，下标）二元组。接着对数组b按照大小为第一关键字排序。然后倒着处理，这就对应着我上面提到的逆向思维，先处理高的石柱。维护区间的关键来了，我是用了一个set命名为s吧，也就是一个去重的集合，首先insert（1）。然后ans数组push（s.size）。因为同样高度的石柱是一起变成0的，所以对同样的数字处理完后就insert一次s.size，就是这一回合石柱的数量。这里怎么理解呢？其实set是用来维护区间的一开始也说了，那么set其实存的是区间的端点下标，一开始1表示［1,n+1）这个区间的用左闭右开方便等下理解。然后每次set插入把石柱的位置和石柱位置+1两个数字，用来表示新的区间端点下标。比如之前的例子1 8 9 5 9 4，在最后一个回合，除了9之外的数字都变成0了，这时候s插入9的下标和9后面的下标，也就是3 4 5 6（有两个9），这时候s中有5个数也就是1 3 4 5 6，说明的是两个9把［1,7）分成了［1,3），［3,4），［4,5），［5,6），［6,7）这5个区间，所以最后一个回合是5根石柱。那么这里用的是set，所以复杂度是O（nlogn），如果用哈希的话是O（n）的。