算法题一
题目描述
输入一个长度为$n$的整型数组($1 \leq n \leq 10^8$),对数组中的每个元素,求其右侧第一个比它大的元素值。若其右侧没有比它大的值,输出-1。
测试样例
测试样例一
输入:[1, 2, 3, 4, 5]
输出:[2, 3, 4, 5, -1]
测试样例二
输入:[4, 3, 2, 1, 5]
输出:[5, 5, 5, 5, -1]
测试样例三
输入:[4, 1, 2, 3, 5, 6]
输出:[5, 2, 3, 5, 6, -1]
解题思路
如下图所示,可以将数组想像成从左向右排列的楼房,每个元素的大小代表着相应楼房的高矮。基于这一想法,可以将本题转化为对每栋楼求右侧第一栋比它高的楼。当我们站在一栋楼的楼顶(图中黄色)向右侧平视时,只能看到比它更高的楼(图中蓝色),同时高楼之间的矮楼会被挡住(图中灰色),因此只需要想办法在每个元素右侧维护这样一个递增的高楼序列(图中蓝色)即可。
因为需要向右侧维护这样一个序列,因此可以考虑从右向左对数组进行遍历,同时使用一个栈来保存右侧的高楼序列。如下图所示,对于每个元素,首先将栈中不大于它的元素逐个出栈,然后观察栈是否为空:若栈为空则右侧没有比它大的元素(返回-1),若栈非空则栈顶元素是右侧每一个比它大的元素,最后将当前元素添加到栈顶。

如下图所示,当走到元素5时,栈中元素分别为[4, 6, 7],首先将栈顶元素4出栈,然后发现栈顶元素6比当前值5大,因此右侧第一个比它大的值为6,同时将当前值5加入到栈中。然后走到元素3时,栈中元素分别为[5, 6, 7],栈顶元素比当前元素值大,因此元素3右侧第一个比它大的值为5,同时将当前值3加入到栈中。

因为对整个数组只遍历了一遍,且每个元素只会入栈并出栈一次,因此该算法整体的时间复杂度为$O(n)$。
解题代码
|
|
算法题二
题目描述
输入一个长度为$n$的非负整型数组$a$($1 \leq n \leq 10^8$),对于每个子数组$a[i..j]$($i \leq j$),定义函数:$f(i,j)=min(a[i..j]) * \sum_{k=i}^{j}a[k]$。请在数组$a$中找到一个子数组$a[i..j]$,使函数$f(i,j)$的值最大,并返回这个最大值。
测试样例
测试样例一
输入:[1, 2, 3, 4, 5]
输出:36([3, 4, 5])
测试样例二
输入:[2, 0, 3, 1, 4, 6, 5]
输出:60([4, 6, 5])
解题思路
$O(n^2)$解题思路
由函数$f(i,j)$的定义可知,本题中主要需解决两个问题:
- 对于子数组$a[i..j]$,快速求出所有元素的和
通过计算前缀和数组,可以在$O(n)$时间复杂度内完成预处理,后续查询时间复杂度$O(1)$ - 对于子数组$a[i..j]$,快速求出所有元素的最小值
基于ST Table(参见《ACM国际大学生程序设计竞赛-算法与实现》4.9节),可以在$O(nlogn)$时间复杂度内完成预处理,后续查询时间复杂度$O(1)$
以上两个问题经预处理后,都可以实现在$O(1)$时间复杂度内查询到答案,但我们仍需要遍历每一个子数组$a[i..j]$,因此算法整体的时间复杂度为$O(n^2)$,并不能满足本题数据量的要求。
$O(n)$解题思路
如果枚举每个子数组来查找最大值,需要的时间复杂度一定会上升到$O(n^2)$,因此需要转换一种枚举策略:将数组中的每个元素$a[k]$作为最小值,找到一个最大的区间$a[i..j]$($i \leq k \leq j$),使得区间内的每个值都不小于$a[k]$。
基于第一题的方法,可以想到如下的预处理策略:对于数组$a$,使用$O(n)$时间计算出辅助数组$left$和$right$,其中$left[k]$保存$a[k]$左侧第一个比它小的值的下标,若不存在则赋值为-1;$right[k]$保存$a[k]$右侧第一个比它小的值的下标,若不存在则赋值为-1。经过预处理之后,就可以在$O(1)$时间复杂度内找到每个元素$a[k]$对应的最大区间,并在$O(1)$时间复杂度内通过前缀和数组求出区间和,因此算法的整体时间复杂度为$O(n)$。
解题代码($O(n)$)
|
|