刷题day12

客官°小女子只卖身不卖艺 2023-10-14 10:02 64阅读 0赞

## 题目一 ##

给定一个只包含正整数的数组arr，arr中任何一个子数组sub,一定都可以算出(sub累加和）\*（sub中的最小值）是什么，那么所有子数组中，这个值最大是多少？

啊 假如说有这么一个数组 3 4 5 6 3 2 7

3来说 以3位子数组的的值怎么说 既然以3为最小值以确定了 那么sub累加和一定要最大 也就是看看这个子数组的左右边界能扩到哪(去找 右边的第一个小于3的值 左边第一个小于它的值)

我们知道 单调栈可以找到 左边的第一个更小(大)值 右边的第一个更小值

思路是 维护一个从小到大栈 遍历每一个元素往里放 如果新加入的值比栈顶的值小 那就把栈顶的元素一个一个弹出 直到这个值放进去 能满足从小到大为止

最后 如果没有值能让这个元素弹出 那说明它右侧没有比它小的 如果这个元素弹出的时候在底部 说明左边没有比它小的

每次弹出这个值的时候 结算一个答案

为什么会在等于的时候结算呢 假如说3 4 5 6 3 2 7这个数组 前面的3的答案我们用3 4 5 6 算 后面的3的答案用 .3 4 5 6 3算 肯定是包含的 或者可以选择使用更复杂的单调栈结构 把两个相同的节点压在一层

public static int max(int [] arr) {
    		int [] sum = new int [arr.length];
    		sum[0] = arr[0];
    		for (int i = 1; i < sum.length; i++) {
    			sum[i]+=arr[i];
    		}
    		int max = 0;
    		Stack<Integer> stack = new Stack<Integer>();
    		for(int i = 0;i<arr.length;i++) {
    			while(!stack.isEmpty()&&arr[stack.peek()]>=arr[i]) {
    				int j = stack.pop();
    				max = Math.max((stack.isEmpty()?sum[i-1]:(sum[i-1]-sum[stack.peek()]))*arr[j], max);
    			}
    			stack.push(i);
    		}
    		while(!stack.isEmpty()) {
    			int j = stack.pop();
    			max = Math.max((stack.isEmpty()?sum[sum.length-1]:(sum[sum.length-1]-sum[stack.peek()]))*arr[j],max);
    		}
    		return max;
    	}

## 第二题 ##

手撕bfprt算法

O(N)复杂度 在一个无序的arr 中找第k小

首先了解一个流程 三分数组+二分

先随机选一个m 以他为划分值 分出<m =m >m 三组区间 然后看看你这个第k小 是在<的区间里 还是在>的区间里 然后再把对应区间三分 直到找到为止(第k小在=的区间里面)

bfprt算法是在这个基础上进行了 优化

也就是说对于这个找m的行为进行了优化 随机选m变成了用算法去找(这个m越在数组中间 复杂度越低)

把arr 五个五个分一组 不足五个一组把 各个小组内部排序

拿每个组的中位数 组成m数组(最后一组为偶数时取上中位)然后再在m数并取中位数 作为它的划分值递归调用bfprt(M,10/N) M是数组 十分之N是五分之N的一半

public static int find(int [] arr,int k) {
    		return bfprt(arr, 0, arr.length-1, k);
    	}
        public static int bfprt(int [] arr,int L,int R, int k) {
        	if (L == R) {
    			return arr[L];
    		}
    		// L...R  每五个数一组
    		// 每一个小组内部排好序
    		// 小组的中位数组成新数组
    		// 这个新数组的中位数返回
    		int pivot = medianOfMedianst(arr, L, R);
    		int[] range = partition(arr, L, R, pivot);
    		if (k >= range[0] && k <= range[1]) {
    			return arr[k];
    		} else if (k < range[0]) {
    			return bfprt(arr, L, range[0] - 1, k);
    		} else {
    			return bfprt(arr, range[1] + 1, R, k);
    		}
    	}
        public static int [] partition(int [] arr,int L,int R,int index) {
        	int less = L-1;
        	int more = R+1;
        	int cur = L;
        	while(less<more) {
        		if(arr[cur]>index){
        			swap(arr, cur, --more);
        		}else if (arr[L]==index) {
    				cur++;
    			}else if (arr[L]<index) {
    				swap(arr, cur++, ++less);
    			}
        	}
        	return new int [] {less+1,more-1};
        }
        
        public static void swap(int[] arr, int i1, int i2) {
    		int tmp = arr[i1];
    		arr[i1] = arr[i2];
    		arr[i2] = tmp;
    	}
        
        public static int medianOfMedianst(int [] arr,int L,int R) {
    	     int size = R-L+1;
    	     int offest = size%5==0?0:1;
    	     int [] tmp = new int [size/5+offest];
    	     for (int team = 0; team < tmp.length; team++) {
    				int teamFirst = L + team * 5;
    				// L ... L + 4
    				// L +5 ... L +9
    				// L +10....L+14
    				tmp[team] = getMedian(arr, teamFirst, Math.min(R, teamFirst + 4));
    			}
    	     return bfprt(tmp,0,tmp.length-1,tmp.length/2);
    	}
        public static int getMedian(int[] arr, int L, int R) {
    		insertionSort(arr, L, R);
    		return arr[(L + R) / 2];
    	}
    
    	public static void insertionSort(int[] arr, int L, int R) {
    		for (int i = L + 1; i <= R; i++) {
    			for (int j = i - 1; j >= L && arr[j] > arr[j + 1]; j--) {
    				swap(arr, j, j + 1);
    			}
    		}
    	}