前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【leetcode刷题】T179-最小差值 II

【leetcode刷题】T179-最小差值 II

作者头像
木又AI帮
发布2019-10-10 11:55:33
3800
发布2019-10-10 11:55:33
举报
文章被收录于专栏:木又AI帮

木又连续日更第20天(20/100)


木又的第179篇leetcode解题报告

贪心类型第8篇解题报告

leetcode第910题:最小差值 II

https://leetcode-cn.com/problems/smallest-range-ii


【题目】

给定一个整数数组 A,对于每个整数 A[i],我们可以选择 x = -K 或是 x = K,并将 x 加到 A[i] 中。

在此过程之后,我们得到一些数组 B。

返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

代码语言:javascript
复制
示例 1:
输入:A = [1], K = 0
输出:0
解释:B = [1]

示例 2:
输入:A = [0,10], K = 2
输出:6
解释:B = [2,8]

示例 3:
输入:A = [1,3,6], K = 3
输出:3
解释:B = [4,6,3]

提示: 1 <= A.length <= 10000 0 <= A[i] <= 10000 0 <= K <= 10000

【思路】

我们需要将数组A进行排序,

如果A[-1] - A[0] <= K,则数组A所有元素都应该同时+K或者-K,否则新数组之间的差值会大于K。

如果A[-1] - A[0] > K,那么元素A[0]到某个元素应该同时+K,该元素到A[-1]应该同时-K,(较大的值减小,较小的值增大)这样新数组之间的差值会较小。遍历每个位置,其之前的元素同时+K,其后的元素同时-K,计算差值并且找到最小差值即可。

寻找差值的过程即为寻找数组最大值和最小值的过程,数组最大值只可能在A[-1]-K和A[i]+K之间出现,最小值只能在A[0]+K和A[i+1]-K出现。

【代码】

python版本

代码语言:javascript
复制
class Solution(object):
    def smallestRangeII(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        if len(A) == 0:
            return 0
        A.sort()
        res = A[-1] - A[0]
        if A[-1] - A[0] <= K:
            return res

        B = [i-K for i in A]
        max0 = A[0]
        min0 = A[-1]
        for i in range(len(A) - 1):
            B[i] += 2 * K
            max0 = max(B[-1], B[i])
            min0 = min(B[0], B[i+1])
            res = min(res, max0 - min0)
        return res

C++版本

代码语言:javascript
复制
class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int res = A.back() - A[0];
        if(res <= K)
            return res;

        int max0, min0;
        for(int i=0; i < A.size()-1; i++){
            max0 = max(A[i] + K, A.back() - K);
            min0 = min(A[0] + K, A[i+1] - K);
            res = min(res, max0 - min0);
        }
        return res;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 木又AI帮 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档