1802.有界数组中指定下标处的最大值

链接：1802.有界数组中指定下标处的最大值
难度：Medium
标签：贪心、二分查找
简介：返回你所构造的数组中的 nums[index] 。

题解 1 - cpp

• 编辑时间：2023-01-04
• 执行用时：8ms
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：双指针。

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        int ans = 1, sum = n, l = index, r = index;
        while (sum + r - l + 1 <= maxSum && !(r == n - 1 && l == 0)) {
            sum += r - l + 1;
            ans += 1;
            r = min(n - 1, r + 1);
            l = max(0, l - 1);
        }
        if (r == n - 1 && l == 0 && sum < maxSum) ans += (maxSum - sum) / n;
        return ans;
    }
};

题解 2 - rust

• 编辑时间：2023-01-04
• 执行用时：8ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn max_value(n: i32, index: i32, max_sum: i32) -> i32 {
        let (mut ans, mut sum, mut l, mut r) = (1, n, index, index);
        while sum + r - l + 1 <= max_sum && !(l == 0 && r == n - 1) {
            sum += r - l + 1;
            ans += 1;
            l = (l - 1).max(0);
            r = (r + 1).min(n - 1);
        }
        if l == 0 && r == n - 1 && sum < max_sum {
            ans += (max_sum - sum) / n;
        }
        ans
    }
}

题解 3 - cpp

• 编辑时间：2023-01-04
• 执行用时：28ms
• 内存消耗：5.7MB
• 编程语言：cpp
• 解法介绍：二分。

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        int l = 1, r = maxSum;
        while (l < r) {
            int m = (l + r + 1) / 2;
            if (check(n, index, m) <= maxSum) l = m;
            else r = m - 1;
        }
        return l;
    }
    long long check(long long n, long long index, long long val) {
        long long ans = val;
        if (val - index >= 1) ans += (val - index + val - 1) * index / 2;
        else ans += (1 + val - 1) * (val - 1) / 2 + (index - (val - 1));
        if (n - 1 - index <= val - 1) ans += (val - (n - 1 - index) + val - 1) * (n - 1 - index) / 2;
        else ans += (1 + val - 1) * (val - 1) / 2 + (n - 1 - index - (val - 1));
        return ans;
    }
};

题解 4 - rust

• 编辑时间：2023-01-04
• 内存消耗：1.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn max_value(n: i32, index: i32, max_sum: i32) -> i32 {
        let (mut l, mut r) = (1, max_sum);
        while l < r {
            let m = (l + r + 1) / 2;
            if Solution::check(n, index, m) <= max_sum  as i64{
                l = m;
            } else {
                r = m - 1;
            }
        }
        l
    }
    fn check(n: i32, index: i32, val: i32) -> i64 {
        let (n, index, val) = (n as i64, index as i64, val as i64);
        let mut ans = val;
        if val - index >= 1 {
            ans += (val - index + val - 1) * index / 2;
        } else {
            ans += (1 + val - 1) * (val - 1) / 2 + (index - (val - 1));
        }
        if n - 1 - index <= val - 1 {
            ans += (val - (n - 1 - index) + val - 1) * (n - 1 - index) / 2;
        } else {
            ans += (1 + val - 1) * (val - 1) / 2 + (n - 1 - index - (val - 1));
        };
        ans
    }
}