快速排序(plus）与单调栈道，力扣912.排序数组力扣215.数组中的第k大个元素力扣17.14最小的k个数单调栈力扣.柱状图中最大的矩形
目录
力扣912.排序数组
力扣215.数组中的第k大个元素
力扣17.14最小的k个数
单调栈
力扣.柱状图中最大的矩形
力扣912.排序数组
快速排序:最重要的就是数据划分，叫做partation
left往后走，假如遇到比key小的，left++是因为，腾出来下一个位置，让i居住，因为假如key是2 nums[i]=1,那么left一定是在key的前一个位置，然后把i和++left换完之后，继续向下遍历
那么假如遇到比key大的情况，需要交换nums[--right]和当前i位置，因为我们只是知道该位置比key大，但是不知道没有遍历的那个元素是大还是小，所以不去动i，其实就是
0-i是已经遍历过的，i-right是没有遍历过的，没有遍历过的需要遍历，遍历过的不动即可。
class Solution {public int[] sortArray(int[] nums) {//传递一个左区间，和一个右边区间qsort(nums,0,nums.length-1);return nums;}public void qsort(int []nums,int l,int r){//0-left left-i. i-rightif(l>=r)return ;//数组分三块int key=nums[new Random().nextInt(r-l+1)+l];int left=l-1,right=r+1,i=l;while(i<right){if(nums[i]<key) swap(nums,++left,i++);else if(nums[i]==key)i++;else swap(nums,--right,i);}qsort(nums,l,left);qsort(nums,right,r);}public void swap(int []nums,int left,int right){int tmp=nums[right];nums[right]=nums[left];nums[left]=tmp;} }
力扣215.数组中的第k大个元素
class Solution {public int findKthLargest(int[] nums, int k) {//堆排序//基于快速选择算法，时间复杂度O(N),基于快排return qsort(nums,0,nums.length-1,k);}public int qsort(int[]nums,int l,int r,int k){if(l==r){//当l==r时候，只有这一个元素，为什么不会l>r的情况//因为查找第几大的时候，不会出现l>r的情况，其实没有边界条件也可以，因为分类已经包含所有可能了。return nums[l];}int key=nums[new Random().nextInt(r-l+1)+l];int left=l-1;int right=r+1;int i=l;while(i<right){if(nums[i]<key)swap(nums,++left,i++);else if(nums[i]==key) i++;else swap(nums,i,--right); }
//分类讨论[l,left],[left+1,right-1],[right,r]//我们需要分别计算出b,c长度int b=right-left-1;int c=r-right+1;if(c>=k) return qsort(nums,right,r,k);else if(b+c>=k) return key;else return qsort(nums,l,left,k-b-c);}public void swap(int[]nums,int left,int right){int tmp=nums[right];nums[right]=nums[left];nums[left]=tmp;}
}力扣17.14最小的k个数
class Solution {public int[] smallestK(int[] arr, int k) {
//最小的k个数，是找大根堆sort(arr,0,arr.length-1,k);int[]a=new int[k];for(int i=0;i<k;i++){a[i]=arr[i];}return a;}public void sort(int []arr,int l,int r,int k){if(l>=r) return ;//先让随机数模区间长度，就是0到n-1int key=arr[new Random().nextInt(r-l+1)+l];int left=l-1;int right=r+1;int i=l;while(i<right){if(key>arr[i]) swap(arr,i++,++left);else if(key==arr[i])i++;else if(key<arr[i]) swap(arr,i,--right);}int a=left-l+1;int b=right-left-1;if(a>k){sort(arr,l,left,k);}else if(a+b>=k){return;}else {sort(arr,right,r,k-a-b);}
}
public void swap(int []nums,int left,int right){int tmp=nums[right];nums[right]=nums[left];nums[left]=tmp;
}}在上面代码，我之前在想，假如我的key是下标，而不是数字，我后面用数字表示会咋样
int key=new Random().nextInt(r-l+1)+l;int left=l-1;int right=r+1;int i=l;while(i<right){if(arr[key]>arr[i]) swap(arr,i++,++left);else if(arr[key]==arr[i])i++;else if(arr[key]<arr[i]) swap(arr,i,--right);}我发现他改变了数组，但是也有问题，就是他的key是下标，而不是数字，换句话说他的这个key是一直变化的按照上述写法，而最上面的正确写法是这个数字保持不变，两侧控制。
单调栈
力扣.柱状图中最大的矩形
单调栈使用，存储两边中第一次遇到的最小值，用单调栈来辅助去找左右两边第一次遇到的最小值，
class Solution {public int largestRectangleArea(int[] heights) { Stack<Integer>stack=new Stack<>();int n=heights.length;int[] left=new int[n];int[] right=new int[n];int count=0;left[0]=-1;stack.add(0);//左边找第一个比她小的for(int i=1;i<n;i++){while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){stack.pop();}if(!stack.isEmpty()&&heights[stack.peek()]<heights[i]){left[i]=stack.peek();}else if(stack.isEmpty()){left[i] = -1;}stack.add(i);}stack.clear();right[n-1]=n;stack.add(n-1);//右边找第一个比她小的for(int i=n-2;i>=0;i--){while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){right[i]=stack.pop();} if(!stack.isEmpty()&&heights[stack.peek()]<heights[i]){right[i]=stack.peek();}else if(stack.isEmpty()){right[i] = n;}stack.add(i);}for(int i=0;i<n;i++){count=Math.max(count,heights[i]*(right[i]-left[i]-1));}return count;
}
}