厦门哪些做鲜花的网站,高校网站网页设计,网址域名注册,哪个网站可以做彩经专家【LetMeFly】908.最小差值 I#xff1a;思维#xff08;遍历#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/smallest-range-i/
给你一个整数数组 nums#xff0c;和一个整数 k 。
在一个操作中#xff0c;您可以选择 0 i nums.length 的…
【LetMeFly】908.最小差值 I思维遍历
力扣题目链接https://leetcode.cn/problems/smallest-range-i/
给你一个整数数组 nums和一个整数 k 。
在一个操作中您可以选择 0 i nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] x 其中 x 是一个范围为 [-k, k] 的整数。对于每个索引 i 最多 只能 应用 一次 此操作。
nums 的 分数 是 nums 中最大和最小元素的差值。
在对 nums 中的每个索引最多应用一次上述操作后返回 nums 的最低 分数 。 示例 1
输入nums [1], k 0
输出0
解释分数是 max(nums) - min(nums) 1 - 1 0。示例 2
输入nums [0,10], k 2
输出6
解释将 nums 改为 [2,8]。分数是 max(nums) - min(nums) 8 - 2 6。示例 3
输入nums [1,3,6], k 3
输出0
解释将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) 4 - 4 0。提示
1 nums.length 1040 nums[i] 1040 k 104
解题方法遍历
这道题应该如何思考呢如何将变化后数组中最大值和最小值之差尽可能地小当然是“大的数尽可能往小的变”、“小的数尽可能往大的变”。
如果 k k k很小那么最大的数 M M M最多减小到 M − k M-k M−k最小的数 m m m最多增加到 m k mk mk最终的最小差值为 M − m − 2 ∗ k M-m-2*k M−m−2∗k如果 k k k足够大 2 k ≥ M − m 2k\geq M-m 2k≥M−m那么所有的数都可以变成相同的数最终最小差值为 0 0 0。
因此答案为 max { 0 , max ( n u m s ) − min ( n u m s ) − 2 k } \max\{0, \max(nums)-\min(nums)-2k\} max{0,max(nums)−min(nums)−2k}
时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
public:int smallestRangeI(vectorint nums, int k) {int M *max_element(nums.begin(), nums.end());int m * min_element(nums.begin(), nums.end());return max(0, M - m - 2 * k);}
};Go
package mainimport slicesfunc smallestRangeI(nums []int, k int) int {return max(0, slices.Max(nums) - slices.Min(nums) - 2 * k)
}Java
class Solution {public int smallestRangeI(int[] nums, int k) {int M nums[0], m nums[0];for (int t : nums) {M Math.max(M, t);m Math.min(m, t);}return Math.max(0, M - m - 2 * k);}
}Python
from typing import Listclass Solution:def smallestRangeI(self, nums: List[int], k: int) - int:return max(0, max(nums) - min(nums) - 2 * k)同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/143112464
