最长湍流数组

最长湍流数组

class Solution {
     public int maxTurbulenceSize(int[] arr) {
        //通过滑动窗口的方式
        int res=1;
        int n=arr.length;
        int left=0,right=0;
        while(right<n-1){
            //对于起点
            if(left==right){
                //起点可能相等
                if(arr[left]==arr[left+1]){
                    left++;
                }
                right++;
            }else{
                //进行扩展
                if(right<n-1&&arr[right-1]<arr[right]&&arr[right]>arr[right+1]){
                    right++;
                }
                else if(right<n-1&&arr[right-1]>arr[right]&&arr[right]<arr[right+1]){
                    right++;
                }else{
                    left=right;
                }

            }
            res=Math.max(res,right-left+1);
        }
        return res;
    }
}

方式二：通过决策维度dp

定义dp[i][0]表示前i个元素 以arr[i]结尾的递减湍流数组
dp[i][1]表示前i个元素，以arr[i]结尾的递增湍流数组

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n=arr.length;
        int[][] dp=new int[n][2];
        dp[0][0]=dp[0][1]=1;
        for(int i=1;i<n;i++){
            dp[i][0]=dp[i][1]=1;//最短长度为1
            if(arr[i]>arr[i-1]){
                dp[i][0]=1;
                dp[i][1]=dp[i-1][0]+1;
            }else if(arr[i]<arr[i-1]){
                dp[i][1]=1;
                dp[i][0]=dp[i-1][1]+1;
            }
        }
        int res=1;
        for(int i=0;i<n;i++){
            res=Math.max(res,Math.max(dp[i][0],dp[i][1]));
        }
        return res;
    }
}

数据流的中位数

class MedianFinder {
    PriorityQueue<Integer> minQueue;
    PriorityQueue<Integer> maxQueue;
    public MedianFinder() {
        minQueue=new PriorityQueue<Integer>((a,b)->a-b);
        maxQueue=new PriorityQueue<Integer>((a,b)->b-a);
    }

    public void addNum(int num) {
        if(minQueue.isEmpty()||num>=minQueue.peek()){
            minQueue.offer(num);
            if(minQueue.size()-maxQueue.size()>1){
                maxQueue.offer(minQueue.poll());
            }
        }else{
            maxQueue.offer(num);
            if(maxQueue.size()>minQueue.size()){
                minQueue.offer(maxQueue.poll());
            }
        }
    }

    public double findMedian() {
        double res=0.0;
        if(minQueue.size()==maxQueue.size()){
            res=(minQueue.peek()+maxQueue.peek())/2.0;
        }else{
            res=minQueue.peek();
        }
        return res;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */