✅给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。

package Ashier.arithmetic.basic_class_01.Code_11_MaxGap;

思路：
数组中又N个数
准备N+1个桶

1. 先遍历数组找到最小值、和最大值，最小值放到 0 号桶，最大值放到 N 号桶
2. 之后取到一个值，这个值就是每个桶存放数据的范围

如：取到的值是9
桶 存储数据的范围
桶0 : [ ( main + 0 9 ) ~ ( main + 1 9 ) )
桶1 : [ ( main + 1 9 ) ~ ( main + 2 9 ) )
桶2 : [ ( main + 2 9 ) ~ ( main + 3 9 ) )
…… ……
桶N : [ ( main + N 9 ) ~ ( main + (N+1) 9 ) ) 该桶其实也就只能存最大值（可能有多个相同最大值）

1. 对于每个桶的信息只有三个信息【该桶中最大值，该桶中最小值，(Boolean)该桶是否有元素进入】
2. 再遍历数组，将每一个元素放到相应的桶中，由于有N个数，桶有N+1个，所以中间必有一个空桶（或多个）
3. 设置一个变量Max = 0，接着遍历桶
4. 每到一个非空桶用该桶最小值减去前一个桶最大值，的到这个差值与Max比较取最大值，
5. 最后这个Max就是我们要找的值

丨设置空桶的目的：
否定我们最大差值不是来自一个桶内部，最大差值一定来自俩个相邻非空桶（中间可以隔又空桶）的前一个桶的最大值和后一个桶的最小值的差。
就是为了杀死最大差值俩个数来自一个桶中的可能性
并不是说最大差值来自空桶俩侧的非空桶。
因为N个数，N+1个桶，必定有空桶，所以最小差值一定是一个桶的容量，但不一定是空桶左右相邻非空桶的差值。

package Ashier.arithmetic.my_exercise;
import java.util.Arrays;
/**
 * 给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序
 *
 * @author shier
 * @date 2021/4/2
 */
public class MaxGap {
    /**
     * 我们写的方法
     * @param arr 目标数组
     * @return 返回所求结果
     */
    static int myMaxGap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int length = arr.length;//数组长度
        int subtract;//最大值-最小值
        //获取数组最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < length; i++) {
            min = Math.min(arr[i], min);
            max = Math.max(arr[i], max);
        }
        subtract = max - min;
        if (subtract == 0) { //差值为0，说明所有元素相同，最大差肯定为0
            return 0;
        }
        //创建length+1个桶，并将元素放入桶中
        int index;//数组中元素应该放在哪个桶的下标
        int[] bucketmin = new int[length + 1]; //桶中最小元素
        int[] bucketmax = new int[length + 1]; //桶中最大元素
        boolean[] buckethave = new boolean[length + 1]; //桶中是否有值
        for (int i = 0; i < length; i++) {//遍历桶
            index = getindex(arr[i], min, length, subtract);//获取元素在桶的下标
//            if(buckethave[index]){//如果桶中放过元素
//                bucketmin[index] = Math.min(arr[i],bucketmin[index]); //覆盖最小值
//                bucketmax[index] = Math.max(arr[i],bucketmax[index]); //覆盖最大值
//            }else {
//                buckethave[index] = true; //标记桶中放过元素
//                bucketmin[index] = arr[i]; //最小值为它
//                bucketmax[index] = arr[i]; //最大值也为它
//            }
            //上面if else可以改写为以下
            bucketmin[index] = buckethave[index] ? Math.min(arr[i], bucketmin[index]) : arr[i];
            bucketmax[index] = buckethave[index] ? Math.max(arr[i], bucketmax[index]) : arr[i];
            buckethave[index] = true;
        }
        //遍历桶找出答案
        int result = 0; //结果，相邻元素最大差值
        int lastmax = bucketmax[0]; //上一个非空桶中的最大值
        for (int i = 0; i < length + 1; i++) {
            if (buckethave[i]) {//如果桶中有元素
                int num = bucketmin[i] - lastmax; //获取差值
                result = Math.max(num, result); //差值比较取最大值
                lastmax = bucketmax[i]; //将该桶最大值赋给lastmax以供下一个非空桶比较
            }
        }
        return result;
    }
    /**
     * 获取元素在桶中的下标
     * @param arri 需要判断的某一个元素
     * @param min 数组最小元素
     * @param length 数组长度
     * @param subtract 数组最大值-最小值差值
     * @return 返回该元素所在桶的下标
     */
    static int getindex(int arri, int min, int length, int subtract) {
        return (int) (((arri - min) * length) / subtract);
    }
    /**
     * 使用绝对正确的方法获取结果（不限要求）与我们自己写的方法结果作比较验证我们的结果是否正确
     * @param arr 传入我们复制过的数组
     * @return 返回正确答案
     */
    public static int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        Arrays.sort(arr);
        int gap = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length; i++) {
            gap = Math.max(arr[i] - arr[i - 1], gap);
        }
        return gap;
    }
    /**
     * 生成随机数组
     * @param maxSize 数组大小
     * @param maxValue 数组元素最大值
     * @return 返回随机数组
     */
    static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }
    /**
     * 复制一份一模一样的数组供另一个方法使用，相互不影响
     * @param arr 目标数组
     * @return 返回复制的新数组
     */
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }
    public static void main(String[] args) {
        int testTime = 10000; //循环验证次数
        int maxSize = 20; //指定数组长度
        int maxValue = 1000; //指定元素最大值
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize,maxValue); //生成随机数组
            int[] arr2 = copyArray(arr); //复制目标数组
            int myresult = myMaxGap(arr); //自己写的方法返回值
            int tureresult = comparator(arr2); //绝对正确的返回值
            if (myresult == tureresult) {
                System.out.println("没毛病铁子！");
            } else {
                System.out.println("完了，又出bug了");
                for (int item: arr) {
                    System.out.print(item + ",");
                }
                System.out.println("你求的结果：" + myresult);
                System.out.println("正确的结果：" + tureresult);
                break;
            }
        }
    }
}

✅用数组结构实现大小固定的队列

package Ashier.arithmetic.class_03.Code_01_Array_To_Stack_Queue

//数组队列
//这里的数组其实是逻辑上的头尾相连的循环数组，就是循环利用数组
//容量固定
其实就是取的指针 start 追着存的指针end跑，可以不设置 size，但是有size判断更方便些，可以把start追着end的逻辑解耦掉。

命名：

• ArrayQueue 数组队列
• peek() 返回第一个传入的元素
• push() 在末尾压入
• poll() 弹出头部

package Ashier.arithmetic.my_exercise;
/**
 * 用数组结构实现大小固定的队列
 *
 * @author shierS
 * @date 2021/4/2
 */
class ArrayQueue {
    Integer[] arr;
    Integer size = 0;  //队列当前容量
    Integer start = 0; //队列当前头部
    Integer end = 0;  //队列当前尾部
    //初始化队列设置容量大小
    public ArrayQueue(Integer size) {
        if(size < 0){
            throw new IllegalArgumentException("The init size is less than 0");
        }
        arr = new Integer[size];
    }
    //返回第一个传入的元素，但不删除
    public Integer peek() {
        if (size == 0) {
            return null;
        }
        return arr[start];
    }
    //在末尾压入
    public void push(int num) {
        if (size == arr.length) { //队列满了，不能添加了，抛出异常
            throw new ArrayIndexOutOfBoundsException("The queue is full");
        }
        arr[end] = num; //将元素添加到尾部
        size++; //容量++
        end = (end == arr.length - 1) ? 0 : end+1;//判断end是否指向了数组末尾，是的化指回到数组头部
    }
    //弹出头部
    public Integer poll() {
        if (size == 0) { //队列中空了
            throw new ArrayIndexOutOfBoundsException("The queue is empty");
        }
        size--; //容量--
        Integer result = arr[start]; //返回头部元素
        start = (start == arr.length - 1) ? 0 : start+1; //移动start标志
        return result;
    }
}
public class ArrayToQueue {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(4);
        arrayQueue.push(1);
        arrayQueue.push(2);
        System.out.println(arrayQueue.peek());
        System.out.println(arrayQueue.poll());
        System.out.println(arrayQueue.peek());
    }
}

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返 回栈中最小元素的操作。

package Ashier.arithmetic.class_03.Code_02_GetMinStack

如何仅用队列结构实现栈结构？

package Ashier.arithmetic.class_03.Code_03_StackAndQueueConvert

如何仅用栈结构实现队列结构?

package Ashier.arithmetic.class_03.Code_03_StackAndQueueConvert