在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第42题：最后的胜者 的题目解析，具体如下：

题目描述

题目等级：简单
知识点：字符串

查看题目：最后的胜者
现在有n个魔法师(2<=n<=100000)，这n个魔法师都有自己的魔法值ai(1<=ai<=1000000000)，他们为了证明自己是最强的魔法师便开始了争夺战，任意一个魔法师都可以对其他的魔法师发起攻击，每次攻击，被攻击的魔法师损失掉的魔法值是攻击者当前的魔法值，当魔法值小于等于0的时候淘汰出局，问最后只剩下一名魔法师时，他的魔法值最少是多少。
输入魔法师数n，和n个数，表示每个魔法师的初始魔法值
输出一个数，在任意的对决中，最后只剩下来一名魔法师的最小的魔法值

示例1
输入：
4
[2,8,6,20]
输出：
2

解题方法

根据题意，可知魔法师在攻击别的魔法师时，自身不会消耗魔法值，只有被攻击时，魔法值才会有损失，损失的魔法值等于攻击者的魔法值。本题要求的就是，任意攻击的情况下，剩下最后一名魔法师的最小魔法值，可以这样解决。

先给各个魔法师按照魔法值从大到小排序，设置min的初始值为当前最小的魔法值，用这个最小的魔法值攻击其他魔法师，直到有其他魔法师的魔法值小于min，这时min的值更新为此时的最小魔法值。然后继续前述攻击方法，直到min为1（最小魔法值不会小于1），或者只剩下最后一名魔法师，此时剩下的魔法师的魔法值即为最小魔法值。

时间复杂度：O(n)
空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：最后的胜者