思考历程:最小总操作取平均即可,后续看到只能增加,所以取下限最大值就是最小次数。第一次循环得到maxNum,第二次循环分别与每一个元素相减并累加得到ret这就是结果。
如何一次遍历呢?
为什么要两次遍历是因为我们要拿到最大值,然后拿max减每一次的值,咱们放到坐标轴中这是纵向思考的。如下图:
class Solution { public: int minMoves(vector<int>& nums) { int max_num=0; int ret=0; for(auto&num:nums)max_num=max(max_num,num); for(auto&num:nums)ret=ret+max_num-num; return ret; } };我们换一个思路我们所求的是虚部的面积和,我们横着求也能得到,此时我们并不需要先求得max,直接用每一次的当前max-当前num再乘上cnt值即可。cnt是我们遍历到第几个元素,在图表中看就是前面缺cnt块当前的差值,排序后更好理解但是实际我们可以不用排序如图:
我们看到在遍历到1的时候它的左侧没有虚部面积得到的就是0,遍历到2左侧虚部的面积就是cnt*一块虚部的面积,遍历到3就是cnt*一块虚部的面积,遍历到5同样也是cnt*一块虚部的面积
所以我们只需要用cnt来记录遍历的次数就是虚部面积的宽,高就是当前num-之前mx。代码如下:
class Solution { public: int minMoves(vector<int>& nums) { int mx=nums[0]; int cnt=0; int ret=0; for(const auto&num:nums){ if(mx<num){ ret+=cnt*(num-mx); mx=num; } ret+=mx-num; cnt++; } return ret; } };至此。