/*
今天的主要内容：
1、桶排序、计数排序的介绍
2、求排序后的数组相邻两个数的最大差值
3、用数组实现大小固定的队列和栈
4、实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
*/
1、桶排序、计数排序的介绍
①非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以，实际中并不经常使用
* 非基于比较的排序总有瓶颈，这种瓶颈来自于他数据状况本身，因此，也就没法作为一个通解被运
用到所有方面
②时间复杂度为O(N),空间复杂度为O(N)
③稳定的排序
几个小点：
- 什么是桶？
答：a. 一种数据状况出现的词频
b. 桶具体的实现可以是数组中的某一个位置，可以是一个队列，也可以
是一个堆；
c. 对数据进行分桶，并不是基于比较的 - 计数排序只是实现了桶排序
补充问题：
2、给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，
且要求不能用非基于比较的排序。
答：此题借用了桶的概念，但是没有进行桶排序
a. 准备桶：
* 如果一个数组中有N个数，则准备N+1个桶
* 先遍历数组，找到最小值和最大值。
** 若最小值和最大值相同，最大差值为0，直接返回
** 若最小值和最大值不同
** 则最小值放到0号桶中，最大值放到N号桶中
** 将最大值和最小值之间的范围等分为N+1份，一个数属于哪个范围，就放到哪
号桶里
** 此时N个数放在N+1个桶里，一定有一个是空桶。
** 相邻两数可能在同一个桶，也可能跨桶
*** 则差值最大的相邻数一定是跨桶，不可能在一个桶里。
** 空桶的左边和右边一定分别存在一个非空的桶
** 空桶左边的非空桶中收集的最大值和空桶右边的非空桶中收集的最小值一定
是两个相邻的数。这两个数的差值一定大于桶所表示的范围。
** 此时我们就不需要处理同一个桶中的两个数之间的差值。因为一定不是最大的
** 此时我们分析空桶只是为了证明：相邻两个数的最大值一定不会来自同一个桶
而是来自于跨桶。
b. 桶中只收集要放在该桶中的数据的最小值和最大值，以及一个Boolean类型的数，用来标识
当前桶中是否进来过数。
c. 从1号桶开始，如果为空，则往下走，每一个非空桶都找前面那个最近的非空桶，找到前一
个非空桶的最大值和当前桶的最小值求一个差值。
代码：
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (maxGap(arr1) != comparator(arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
public static int maxGap(int[] arr){
//判断数组合法性
if (arr == null || arr.length < 2) {
return 0 ;
}
//遍历数组求数组中的最小值和最大值的下标
int len = arr.length;
int minIndex = 0;
int maxIndex = 0;
for (int i = 0; i < len; i++) {
if (less(arr, i, minIndex)) {
minIndex = i;
}
if (less(arr, maxIndex, i)) {
maxIndex = i;
}
}
//求出最小值和最大值
int min = arr[minIndex];
int max = arr[maxIndex];
//判断最小值和最大值
if (min == max) {
return 0;
}
//设计桶
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
int bid = 0;
//重新遍历整个数组，将数进行分桶
for (int i = 0; i < len; i++) {
bid = bucket(arr[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid],arr[i]) : arr[i]; //更新桶中的最小值
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],arr[i]) : arr[i]; //更新桶中的最大值
hasNum[bid] = true;
}
//求相邻数的最大差值
/*
* 从1号桶开始，如果为空，则往下走，每一个非空桶都找前面那个最近的非空桶，
* 找到前一个非空桶的最大值和当前桶的最小值求一个差值。
* */
int result = 0;
int lastMax = maxs[0]; //将第一个桶中的最大值作为初始的待比较的非空桶的最大值
for (int i = 1; i <= len; i++) {
if (hasNum[i]) { //当前桶不空
result = Math.max(result, mins[i] - lastMax); //当前非空桶的最小值 - 前一个非空桶的最大值
lastMax = maxs[i];
}
}
return result;
}
/*
- 比较数组中两个数的大小
- */
private static boolean less(int[] arr, int i, int j) {
return arr[i] - arr[j] < 0;
}
/**
- 将数据进行分桶
*/
private static int bucket(long num, long len,long min, long max) {
return (int) ((num - min) * len / (max - min));
}
// for test
public static int comparator(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int gap = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
gap = Math.max(nums[i] - nums[i - 1], gap);
}
return gap;
}
// for test
public 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;
}
// for test
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;
}
3、用数组结构实现大小固定的队列和栈
public static class ArrayStack<T extends Comparable<T>>{
private static int maxSize = 10; //当前栈的大小
private static Comparable[] arr;
private static int N = 0; //当前栈中的元素个数
public ArrayStack() {
init(maxSize);
}
public ArrayStack(int maxSize){
this.maxSize = maxSize;
init(maxSize);
}
private void init(int maxSize) {
arr = new Comparable[maxSize];
}
public static boolean isEmpty(){
return N == 0;
}
public static int size(){
return N;
}
public static Comparable peek(){
if (N == 0) {
return null;
}
return arr[N - 1];
}
public static void push(Comparable item) {
if (N == maxSize) {
throw new ArrayIndexOutOfBoundsException("The stack is full");
}
arr[N++] = item;
}
public static Comparable pop(){
if (!isEmpty()) {
return arr[--N];
}else
throw new ArrayIndexOutOfBoundsException("The stack is empty");
}
}
/*
队列的一些操作:
- 队列为空：rear == front
- 队列为满：(rear + 1) % maxSize == front //（基于给队列留一个空闲位置而实现，不然和队列为空时条件重合）
- 队列长度：(rear - front) % maxSize
-
*/
public static class ArrayQueue<T extends Comparable<T>>{
private static int maxSize = 10;
private static Comparable[] arr;
private static int front;
private static int rear;ArrayQueue(){
init(maxSize);
}ArrayQueue(int maxSize) {
init(maxSize);
}private void init(int maxSize) {
arr = new Comparable[maxSize];
front = rear = 0;
}public static boolean isEmpty(){
return rear == front;
}public static int size(){
return (rear - front) % maxSize;
}public static void enqueue(Comparable item) {
if (isFull()) {
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
arr[rear] = item;
rear = (rear + 1) % maxSize;
}public static Comparable dequeue(){
if (isEmpty()) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}Comparable tmp = arr[front]; front = (front + 1)%maxSize; return tmp;}
private static boolean isFull() {
return ((rear + 1) % maxSize) == front;
}public Comparable peek() {
return arr[front];
}
}
public static void main(String[] args) {
Integer[] a = {1,2,3,4,5,6};
ArrayStack<Integer> stack = new ArrayStack<>(a.length);
for (int i = 0; i < a.length; i++) {
stack.push(a[i]);
}
System.out.print("栈的大小为：" + stack.size()+ " 输出为：");
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
System.out.println();
ArrayQueue<Integer> queue = new ArrayQueue<>(6);
for (int i = 0; i < a.length; i++) {
queue.enqueue(a[i]);
}
System.out.print("队列的大小为" + queue.size() + " 输出为：");
while (!queue.isEmpty()) {
System.out.print(queue.dequeue() + " ");
}
System.out.println();
}
4、实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】
* pop、push、getMin操作的时间复杂度都是O(1)。
* 设计的栈类型可以使用现成的栈结构。
思路：
* 此时利用两个栈：stackData和stackMin
** stackData中压入每一次进来的数据
** stackMin中存放当前栈中最小值
* 进来一个数据item
** 压入stackData栈，stackData.push(item)
** 如果stackMin栈为空，则压入stackMin栈
如果stackMin不为空且item比stackMin的栈顶元素大，则将stackMin中栈顶元素再一次压栈
如果stackMin不为空且item比stackMin的栈顶元素小，则将item进行压栈
代码：
public static class MinStack<T extends Comparable<T>>{
private static Stack<Comparable> stackData;
private static Stack<Comparable> stackMin;
private static int N = 0;
public MinStack(){
init();
}
private void init() {
this.stackData = new Stack<Comparable>();
this.stackMin = new Stack<Comparable>();
}
public static int size() {
return N;
}
public static void push(Comparable item) {
stackData.push(item); //将数据直接压入stackData栈中
N++;
if(!stackMin .isEmpty() && less(stackMin.peek(),item)){ //若新加入的数据比stackMin中栈顶数据大
stackMin.push(stackMin.peek()); //将stackMin中的栈顶元素再进行一次压栈
}else{ //若新加入的数据比stackMin中栈顶数据大
stackMin.push(item); //将新元素压栈到stackMin栈中
}
}
public static Comparable pop(){
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
Comparable item = stackData.pop();
N--;
stackMin.pop();
return item;
}
public static Comparable getMin(){
return stackMin.peek();
}
private static boolean less(Comparable i, Comparable j) {
return i.compareTo(j) < 0;
}
}
public static void main(String[] args) {
MinStack stack1 = new MinStack();
stack1.push(3);
System.out.println(stack1.getMin());
stack1.push(4);
System.out.println(stack1.getMin());
stack1.push(1);
System.out.println(stack1.getMin());
System.out.println(stack1.pop());
System.out.println(stack1.getMin());
System.out.println("=============");
MinStack stack2 = new MinStack();
stack2.push(3);
System.out.println(stack2.getMin());
stack2.push(4);
System.out.println(stack2.getMin());
stack2.push(1);
System.out.println(stack2.getMin());
System.out.println(stack2.pop());
System.out.println(stack2.getMin());
}
5、如何仅用队列结构实现栈结构？ 如何仅用栈结构实现队列结构？
思路一：
* 如何仅用队列结构实现栈结构？
** 准备两个队列，queueData和queueHelp队列
*** queueData用来入队每一个新进来的元素，数永远只进data队列
*** 当需要取出一个元素时，我们将除了queueData中最后一个元素外出队到queueHelp中
然后从queueData中取出那个剩下的队尾的元素
*** 每一次的pop操作之后，都要交换data和help的指针
思路二：
* 如何仅用栈结构实现队列结构？
** 准备两个栈，stackPush和stackPop栈
*** stackPush用来入栈每一个新进来的元素，数永远只被push到stackPush中
*** 当需要取出一个元素时，我们就从stackPop中进行获取
①要注意：把stackPush栈中的内容全部出栈到stackPop中
②如果stackPop中有元素，则一定不要将stackPush中数据倒到stackPop中
代码：
public static class TwoQueuesStack{
private static Queue<Comparable> queueData;
private static Queue<Comparable> queueHelp;
TwoQueuesStack(){
queueData = new LinkedList<>();
queueHelp = new LinkedList<>();
}
public static void push(Comparable item){
queueData.add(item);
}
public static Comparable peek(){
if (queueData.isEmpty()) {
throw new RuntimeException("Stack is Empty");
}
while (queueData.size() > 1) { //将queueData队列中除了队尾的元素外都出队到queueHelp中
queueHelp.add(queueData.poll());
}
Comparable result = queueData.poll();
queueHelp.add(result); //因为只是查看，因此还要将队尾元素再添加到queueHelp队列中
exch(); //交换queueData和queueHelp
return result;
}
public static Comparable pop(){
if (queueData.isEmpty()) {
throw new RuntimeException("Stack is Empty");
}
while (queueData.size() > 1) { //将queueData队列中除了队尾的元素外都出队到queueHelp中
queueHelp.add(queueData.poll());
}
Comparable result = queueData.poll();
exch(); //交换queueData和queueHelp
return result;
}
public static int size(){
return (queueHelp.size() + queueData.size());
}
/*
* 交换queueData和queueHelp
* */
private static void exch() {
Queue<Comparable> t = queueData;
queueData = queueHelp;
queueHelp = t;
}
}
public static class TwoStacksQueue{
private static Stack<Comparable> stackPush;
private static Stack<Comparable> stackPop;
TwoStacksQueue(){
stackPush = new Stack<>();
stackPop = new Stack<>();
}
public static int size(){
return stackPush.size() + stackPop.size();
}
public static void enqueue(Comparable item){
stackPush.push(item);
}
public static Comparable dequeue(){
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}
/*
* 当需要取出一个元素时，我们就从stackPop中进行获取
①要注意：把stackPush栈中的内容全部出栈到stackPop中
②如果stackPop中有元素，则一定不要将stackPush中数据倒到stackPop中
* */
private static void pushToPop() {
if (stackPop.isEmpty()) { //如果stackPop中有元素，则一定不要将stackPush中数据倒到stackPop中
return;
}
while(!stackPush.isEmpty())
stackPop.push(stackPush.pop());
}
