小红书5月7日算法笔试编程题
第二问是个脑筋急转弯，不是典型的算法题。时间复杂度和空间复杂度都是 O(n)。
现有 n 个整数 a1, ..., an，每次操作可以删除一段下标连续的数字（例如 a2, a3, a4），但删除后剩余的整数个数必须大于 0。请进行最多 k 次这样的操作，使得最后剩余的整数中的最小值最大，并将这个最大的最小值输出。（1≤n,k≤10^5）
输入数据有两行，为
n k
a1 ... an以下为一个样例
输入：
5 1
58 63 61 89 57输出：
58
对问题的空间进行合理划分是本题的关键：
- 当 k > 1 时，只要找到最大值所在位置，并将两侧的片段删除即可，这样剩下的就是全局最大值。
- 当 k = 1 时，如果删除中间的一段子列，那么剩下的片段为 [头1, ..., 尾1] 和 [头2, ..., 尾2]，有如下关系
min([头1,...,尾1])≤头1
min([头2,...,尾2])≤尾2
min(剩下的片段)≤max(头1,尾2)
而目标函数的上界（不等式的右侧） max(头1,尾2) 可以通过一次切割（保留最左的头1，或保留最右的尾2）实现，因此切中间的子片段一定不优于仅保留 a1,an 中的最大值，同样可以发现保留左侧或保留右侧也一定不优于仅保留 a1, an 中的最大值。 代码如下
n, k = [int(x) for x in input().split()] a = [int(x) for x in input().split()] if k > 1: print(max(a)) else: print(max(a[0], a[-1])#小红书##小红书笔试##小红书24届实习招聘##24届实习#
类似资料：