LeetCode_贪心_二分搜索_中等_1802.有界数组中指定下标处的最大值

左手的ㄟ右手 2023-10-07 22:31 27阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标从 0 开始计数）：

*  nums.length == n；
 *  nums\[i\] 是 正整数 ，其中 0 <= i < n；
 *  abs(nums\[i\] - nums\[i + 1\]) <= 1 ，其中 0 <= i < n - 1；
 *  nums 中所有元素之和不超过 maxSum；
 *  nums\[index\] 的值被最大化；  
    返回你所构造的数组中的 nums\[index\] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

**示例 1：**  
输入：n = 4, index = 2, maxSum = 6  
输出：2  
解释：数组 \[1,1,2,1\] 和 \[1,2,2,1\] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

**示例 2：**  
输入：n = 6, index = 1, maxSum = 10  
输出：3

提示：  
1 <= n <= maxSum <= 109  
0 <= index < n

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array

## 2.思路 ##

（1）暴力穷举法  
① 用 res 来表示 nums\[index\]，并从 res = maxSum 开始，穷举 res，以保证 nums\[index\] 的值被最大化；  
② 在穷举的过程中，用 sum 表示数组 nums 的所有元素之和，如果 sum <= maxSum，则说明找到了满足题目所有条件的数组 nums，此时直接返回 res 即可；否则 res–，继续下一轮穷举；  
③ 当 res < 1 时，结束穷举；  
需要注意的是，该方法的时间复杂度较高，为 O(mn)，所以在 LeetCode 中提交会出现“超出时间限制”的情况！

（2）贪心算法 & 二分搜索  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int maxValue(int n, int index, int maxSum) {
        
            // 用 res 来表示 nums[index] 
            int res = maxSum;
            //从 res = maxSum 开始，枚举 res，以保证 nums[index] 的值被最大化
            while (res >= 1) {
        
                // sum 表示数组 nums 的所有元素之和
                long sum = res;
                //计算 nums[index + 1...0] 的和
                for (int i = index + 1; i < n; i++) {
        
                    sum += Math.max(res - i + index, 1);
                }
                //计算 nums[0...index - 1] 的和
                for (int i = index - 1; i >= 0; i--) {
        
                    sum += Math.max(res - index + i, 1);
                }
                //保证数组 nums 的元素之和不超过 maxSum
                if (sum <= maxSum) {
        
                    return res;
                }
                res--;
            }
            return -1;
        }
    }

//思路2————贪心算法 & 二分搜索
    class Solution {
        
        public int maxValue(int n, int index, int maxSum) {
        
            int leftCnt = index;
            int rightCnt = n - index - 1;
            //二分查找的左右边界(1 <= nums[index] <= maxSum)
            int left = 1;
            int right = maxSum;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                long sum = mid + calPartSum(mid, leftCnt) + calPartSum(mid, rightCnt);
                if (sum > maxSum) {
        
                    right = mid - 1;
                } else {
        
                    left = mid + 1;
                }
            }
            return left - 1;
        }
        
        private long calPartSum(int maxNum, int cnt) {
        
            if (maxNum > cnt) {
        
                /*
                    [maxNum - 1, maxNum - 2, ..., maxNum - cnt]，一共有 cnt 个数
                    可直接使用等差数列的求和公式：(首项 + 尾项) * 项数 / 2  
                */
                return (long) (maxNum - 1 + maxNum - cnt) * cnt / 2;
            } else {
        
                /*
                    maxNum <= cnt
                    [maxNum - 1, maxNum - 2, ..., maxNum - cnt = 1, 1, ..., 1]，一共有 cnt 个数
                    分两部分求和：[maxNum - 1, maxNum - 2, ..., 1] + [1, 1, ..., 1]，分别有 maxNum - 1 和 cnt - (maxNum - 1) 个数
                */
                return (long) (maxNum - 1 + 1) * (maxNum - 1) / 2 + cnt - (maxNum - 1);
            }
        }
    }

[Link 1]: https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/solution/you-jie-shu-zu-zhong-zhi-ding-xia-biao-c-aav4/