快速排序(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-right if(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-1
int 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;
}
}