滑动窗口 优先队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
 //通过优先队列  堆进行维护
        int n=nums.length;
        PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]==o2[0]? o2[1]-o1[1]:o2[0]-o1[0];
            }
        });
        //将开始的长度k放入队列
        for(int i=0;i<k;i++){
            queue.offer(new int[]{nums[i],i});
        }
        //创建结果数组
        int[] res=new int[n-k+1];
        res[0]=queue.peek()[0];
        //维护堆
        for(int i=k;i<nums.length;i++){
            queue.offer(new int[]{nums[i],i});
            while(queue.peek()[1]<=(i-k)){
                queue.poll();
            }
            res[i-k+1]=queue.peek()[0];
        }
        return res;
    }
}

满足不等式的最大值

满足不等式的最大值

class Solution {
     public int findMaxValueOfEquation(int[][] points, int k) {
        //枚举当前点，通过优先队列维护当前i点之前的k个点最大的坐标差值
        PriorityQueue<int[]> queue=new PriorityQueue<int[]>((a,b)->b[0]-a[0]);
        //第一个点
        queue.offer(new int[]{points[0][1]-points[0][0],points[0][0]});
        int res=Integer.MIN_VALUE;
        for(int i=1;i<points.length;i++){
            //将不符合要求的点出队
            while(!queue.isEmpty()&&(points[i][0]-queue.peek()[1])>k){
                queue.poll();
            }
            if (!queue.isEmpty()) {
                res=Math.max(res,points[i][0]+points[i][1]+queue.peek()[0]);   
            }
            //将当前点加入队列
            queue.offer(new int[]{points[i][1]-points[i][0],points[i][0]});
        }
        return res;
    }
}

最大的团队表现值 两个变量取极值

最大的团队表现值
类似于解二元一次不定方程，首先枚举一个未知数x 对于每一个x,要想使目标接近，然后y的取值范围可以固定

class Solution {
     public int maxPerformance(int n,int[] speed,int[] efficiency,int k){
        int MOD=1000000007;
        PriorityQueue<long[]> queue=new PriorityQueue<long[]>((a,b)->Long.compare(b[0],a[0]));
        for(int i=0;i<n;i++){
            queue.offer(new long[]{efficiency[i],speed[i]});
        }
        //小根堆
        PriorityQueue<Long> q=new PriorityQueue<>((a,b)->Long.compare(a,b));
        long res=Integer.MIN_VALUE;
        //通过sum维护堆中和
        long sum=0;
        while (!queue.isEmpty()) {
           long[] node=queue.poll();
           //加入堆，维护k
           //维护结果
           //对q进行求和
           if(q.size()>k-1){
               sum-=q.poll();
           }
           sum=(sum+node[1]);
           res=Math.max(res,node[0]*(sum));//将所有的结果进行比较取最大，之前不能将结果取MOD余
           q.offer(node[1]);         
        }
        return (int)(res%MOD);
    }
}