Yang's Website

题目

一个数组中有 N 个元素，找出最大数量的元素，使这些元素最大值和最小值的差不超过 K

思路

先将数组排序，用一个循环遍历数组，每次循环中有一个小循环找到当前元素和与当前元素相差小于 K 的元素的最远距离，并记录距离的最大值

复杂度分析

排序的复杂度为 O(n logn)，嵌套循环的复杂度为 O(n^2)。N 的范围是 [1, 1000]，K 的范围是 [0, 10000]，因此最多会执行大约 10^7 次操作，不会超时

题目

一个升序序列中有一个不符合升序条件的元素，每次交换两个元素，求使序列恢复升序最小的步骤数

思路

先找到不符合要求元素的位置和它应该在的位置，然后从该元素位置向原位置遍历，途中若某元素与上一个元素不相同，则步骤数加一。

复杂度分析

找到不符合要求元素位置和原位置的复杂度均为 O(n)，遍历的复杂度也为 O(n)，因此总复杂度为 O(n)。元素数量最大为 100，因此不会超时。

题目

已知三个容量分别为 X，Y 和 M 的桶，且 X < Y < M。有两种方式可以往桶 M 中倒牛奶：

1. 装满桶 X 并全部倒入桶 M
2. 装满桶 Y 并全部倒入桶 M

求不溢出的情况下，桶 M 最多能装多少牛奶。

思路

先全部用桶 Y 来倒，再逐渐把 Y 换成 X，并记录所有情况中倒最大值

复杂度分析

M 的范围为 [1, 1000]，而 X 和 Y 都小于 M，直接枚举最坏情况下，时间复杂度大约为 O(10^3)，因此不会超时