Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/11 00:14)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串343/719 (看更多)

https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/description/ 1802. Maximum Value at a Given Index in a Bounded Array 給你三個數字n, index, maxSum，我們必須找出一個陣列 nums 滿足： 1.陣列大小為n 2.陣列所有元素之和小於maxSum 3.nums[i] 和 nums[i + 1] 相差不多於1 4.nums[index] 的大小盡可能大 5.nums[i] >= 1 Example 1: Input: n = 4, index = 2, maxSum = 6 Output: 2 Explanation: nums = [1,2,2,1] is one array that satisfies all the conditions. There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2]. Example 2: Input: n = 6, index = 1, maxSum = 10 Output: 3 思路： 1.因為nums[index]要盡可能大，他的值可能是 0 ~ maxSum，在一定的範圍中找滿足條件的最大值我們可以使用二分搜索。 2.mid 是中間和，我們判斷他的左邊和右邊的陣列和相加之後是否小於等於 maxSum，我們需要一個方法可以快速的求和。 3.因為中間要盡可能大又不能超過maxSum，所以旁邊必須要盡可能小，為了滿足連續的元素要相差不為1，中心點左右兩邊的陣列值必定會是一個越往左(右) 越遞減的數列，遞減到1之後後面都會是1（例如：5, 4, 3, ..., 1, 1, 1）。可以分成兩個情況：一、mid的值大於元素個數n：可以用求和公式快速找出範圍內的和 sum = (mid - n + mid) * n / 2 二、mid的值小於元素個數n：部分和用求和公式，剩下的元素全補1 sum = (mid + 1) * mid / 2 + n - mid 4.每次依照sum判斷當前的值是否不會超出maxSum，往左邊界二分查找，這邊求 mid的時候要額外 + 1，否則當範圍值為偶數時會無窮迴圈，例如： left = 8, right = 10; (left + right)/2 = 8; 5.返回左邊界。 Java Code： -------------------------------------------------------- class Solution { public int maxValue(int n, int index, int maxSum) { int left = 1; int right = maxSum; while (left < right) { int mid = (left + right + 1) / 2; long sum = getSum(mid - 1, index) + getSum(mid, n - index) ; if (sum <= maxSum) { left = mid; } else { right = mid - 1; } } return left; } private long getSum(long x, int n) { return x >= n ? (x + x - n + 1) * n / 2 : (x + 1) * x / 2 + n - x; } } -------------------------------------------------------- 二分查找真的好難= = -- https://i.imgur.com/bFRiqA3.jpg