问题描述
来源：LeetCode第1979题
难度：简单
给你一个整数数组nums，返回数组中最大数和最小数的最大公约数。
两个数的最大公约数是能够被两个数整除的最大正整数。
示例 1：
输入：nums = [2,5,6,9,10]
输出：2
解释：
nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2
示例 2：
输入：nums = [7,5,6,8,3]
输出：1
解释：
nums 中最小的数是 3
nums 中最大的数是 8
3 和 8 的最大公约数是 1
示例 3：
输入：nums = [3,3]
输出：3
解释：
nums 中最小的数是 3
nums 中最大的数是 3
3 和 3 的最大公约数是 3
提示：
2<=nums.length<=1000
1<=nums[i]<=1000
辗转相除法解决
这题让求的是数组中最大值和最小值的最大公约数。数组中的最大值和最小值很容易求，只需要一次遍历即可。这里关键的地方是求两个数字的最大公约数。求最大公约数最常见的方式就是使用欧几里得算法，也称为辗转相除法。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
实际上就是如果a>b，那么a和b的最大公约数就是b和a%b的最大公约数。我们这样一步步缩小a和b的值，直到a能被b整除的时候，这样他们的最大公约数就是b，代码如下
public static int gcd(int a, int b) {
//如果a能被b整除，直接返回b的值
if (a % b == 0)
return b;
return gcd(b, a % b);
}
举个例子，比如我们求33和12的最大公约数。
（33,12）→（12,9）→（9,3）
3能够被9整除，所以33和12的最大公约数是3。
只写公式不写推导过程就是耍流氓，我们这里来推导一下辗转相除法为什么可以解决最大公约数问题。
假设a和b的最大公约数是c，也就是说a和b都能够被c整除。那么他们的线性组合ax±by也一定能被c整除（x和y都是整数），这个应该都能理解吧，如果不能理解我再来给你证明一下，假设a=mc，b=nc，那么ax±by=mxc±nyc，都有一个公约数c，所以肯定能被c整除。
辗转相除法的思路就是假设a>b，a/b=t余r，整理一下就是a-bt=r，上面我们说过如果a和b的最大公约数是c，那么那么他们的线性组合一定能被c整除，也就是a-bt一定能被c整除，所以r也一定能被c整除。这个时候求a和b的最大公约数我们就可以变成求b和r的最大公约数了。
证明到这里就完了吗，其实并没有，上面我们只是证明了c是b和r的公约数，但没有证明是最大的，这里需要证明一下。
假设a=mc，b=nc，那么r=a-bt=mc-nct=(m-nt)c，上面我们证明了a和b的最大公约数也是b和r的公约数，这里我们只需要证明m-nt和n是互质的就可以证明c也是r和b的最大公约数了。
r=(m-nt)c
b=nc
假设b和r不互质，他们有公约数d，那么m-nt=xd，n=yd，则m=nt+xd=ydt+xd=(yt+x)d，所以
a=mc=(yt+x)dc
b=nc=ydc
通过上面我们看到a和b都有公约数dc，因为a和b的最大公约数是c，所以d必定是1。也就是说m-nt和n只有公约数1，也就是说他们是互质的。所以我们可以得出c也是b和r的最大公约数。
最后我们再来看下这题的代码。
public int findGCD(int[] nums) {
int max = nums[0];
int min = nums[0];
for (int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
return gcd(max, min);
}
private int gcd(int a, int b) {
//如果a能被b整除，直接返回b的值
if (a % b == 0)
return b;
return gcd(b, a % b);
}
补充：
我们来思考这样一个问题，任何矩形都可以分割成长度为1的正方形（矩形的宽和高必须都是整数）。假设我们把矩形的长和宽分别记为a和b，那么求a和b的最大公约数就是求矩形所能分割的最大正方形的边长。注意：这里分割的正方形必须全部相等，你不能像下面这样分。
正确的分割方式如下，也就是说所有分割的正方形大小必须相等，这样正方形的边长才是长和宽的最大公约数，如下图所示。
搞懂了这一点，在来理解辗转相除法就容易的多。我们只需要把矩形不断砍掉和矩形高度一样的正方形（假设矩形宽度值比高度值大），直到不能砍为止，那么剩下这个小的矩形宽高的最大公约数也就是原来矩形宽高的最大公约数。我们就用求10和4的最大公约数画个图来看一下
联系客服
