go

robot · robot · commit 55bd37967d7f · 2023-10-17T19:18:16.000+08:00
diff --git a/README.md b/README.md
@@ -431,6 +431,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [2592. 最大化数组的伟大值](./problems/2592.maximize-greatness-of-an-array.md)
 - [2593. 标记所有元素后数组的分数](./problems/2593.find-score-of-an-array-after-marking-all-elements.md)
 - [2817. 限制条件下元素之间的最小绝对差](./problems/2817.minimum-absolute-difference-between-elements-with-constraint.md)
+- [2866. 美丽塔 II](./problems/2866.beautiful-towers-ii.md)
 - [5935. 适合打劫银行的日子](./problems/5935.find-good-days-to-rob-the-bank.md)
 - [5936. 引爆最多的炸弹](./problems/5936.detonate-the-maximum-bombs.md)
 - [5965. 相同元素的间隔之和](./problems/5965.intervals-between-identical-elements.md)
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -276,6 +276,7 @@
   - [2592. 最大化数组的伟大值](./problems/2592.maximize-greatness-of-an-array.md)
   - [2593. 标记所有元素后数组的分数](./problems/2593.find-score-of-an-array-after-marking-all-elements.md)
   - [2817. 限制条件下元素之间的最小绝对差](./problems/2817.minimum-absolute-difference-between-elements-with-constraint.md)
+  - [2866. 美丽塔 II](./problems/2866.beautiful-towers-ii.md)
   - [5935. 适合打劫银行的日子](./problems/5935.find-good-days-to-rob-the-bank.md)
   - [5936. 引爆最多的炸弹](./problems/5936.detonate-the-maximum-bombs.md)
   - [5965. 相同元素的间隔之和](./problems/5965.intervals-between-identical-elements.md)
diff --git a/problems/2009.minimum-number-of-operations-to-make-array-continuous.md b/problems/2009.minimum-number-of-operations-to-make-array-continuous.md
@@ -66,20 +66,24 @@ nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
 
 朴素的思路是枚举所有的区间 [a,b] 其中 a 和 b 为区间 [min(nums),max(nums)] 中的两个数。这种思路的时间复杂度是 $O(v^2)$，其中 v 为 nums 的值域。看一下数据范围，很明显会超时。
 
-我们可以先对数组排序，这样就可以二分找答案，使得时间复杂度降低。看下时间复杂度排序的时间是可以允许的，因此这种解决可以 ac。
+假设我们最终形成的连续区间是 [l, r]，那么 nums[i] 一定有一个是在端点的，因为如果都不在端点，变成在端点不会使得答案更差。这样我们可以枚举 nums[i] 作为 l 或者 r，分别判断在这种情况下我们可以保留的数字个数最多是多少。
 
- 具体地：
+为了减少时间复杂度，我们可以先对数组排序，这样就可以二分找答案，使得时间复杂度降低。看下时间复杂度排序的时间是可以允许的，因此这种解决可以 ac。
+
+具体地：
 
 - 对数组去重
 - 对数组排序
-- 遍历 nums，对于每一个 num 我们都二分找到最左和最右的**满足值域差小于等于 old_n 的索引**，其中 old_n 为去重前的 nums 长度。简单来说，我们需要找到满足值在 [x,num] 范围的最左 x 和满足值在 [num,y] 范围的最右 y
-- 满足两个值域范围的区间我们找到了，那么答案区间长度的最大值，也就是 n - 区间长度中的**最小值**
+- 遍历 nums，对于每一个 num 我们需要找到其作为左端点时，那么右端点就是 v + on - 1，于是我们在这个数组中找值在 num 和 v + on - 1 的有多少个，这些都是可以保留的。剩下的我们需要通过替换得到。 num 作为右端点也是同理。这两种我们需要找最优的。所有 i 的最优解就是答案。
+
 
- 具体参考下方代码。
+具体参考下方代码。
 
 ## 关键点
 
 - 反向思考，题目要找最少操作数，其实就是找最多保留多少个数
+- 对于每一个 num 我们需要找到其作为左端点时，那么右端点就是 v + on - 1，于是我们在这个数组中找值在 num 和 v + on - 1 的有多少个，这些都是可以保留的
+- 排序 + 二分 减少时间复杂度
 
 ## 代码
 
@@ -99,8 +103,9 @@ class Solution:
         nums.sort()
         n = len(nums)
         for i, v in enumerate(nums):
-            r = bisect.bisect_right(nums, v + on - 1)
-            l = bisect.bisect_left(nums, v - on + 1)
+            # nums[i] 一定有一个是在端点的，如果都不在端点，变成在端点不会使得答案更差
+            r = bisect.bisect_right(nums, v + on - 1) # 枚举 i 作为左端点
+            l = bisect.bisect_left(nums, v - on + 1) # 枚举 i 作为右端点
             ans = min(ans, n - (r - i), n - (i - l + 1))
         return ans + (on - n)
 
