首页 > 其他 > 详细

Smallest Range II

时间:2020-01-21 22:06:40      阅读:28      评论:0      收藏:0      [点我收藏+]

标签:tran   感觉   alt   public   arp   highlight   

2020-01-21 21:43:52

问题描述:

技术分享图片

技术分享图片

问题求解:

这个题目还是有点难度的,感觉很巧妙也很难想到。

整体的思路如下:

1. 首先原问题等价于 +0 / + 2*K

2. 那么res = Max - Min

3. 不断更新Max,Min期望得到更小的res

    public int smallestRangeII(int[] A, int K) {
        int n = A.length;
        Arrays.sort(A);
        int max = A[0];
        int min = A[0];
        for (int num : A) {
            if (num > max) max = num;
            if (num < min) min = num;
        }
        int res = max - min;
        for (int i = 0; i < n - 1; i++) {
            max = Math.max(A[n - 1], A[i] + 2 * K);
            min = Math.min(A[0] + 2 * K, A[i + 1]);
            res = Math.min(res, max - min);
        }
        return res;
    }

  

Smallest Range II

标签:tran   感觉   alt   public   arp   highlight   

原文:https://www.cnblogs.com/hyserendipity/p/12227140.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号