1.搜寻插入地位

https://leetcode-cn.com/problems/search-insert-position/

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                return mid;
            }
        }
        return left;
    }
}

2.搜寻二维矩阵

https://leetcode-cn.com/problems/search-a-2d-matrix/

public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix.length == 0)
        return false;
    int row = 0, col = matrix[0].length-1;
    while(row < matrix.length && col >= 0){
        if(matrix[row][col] < target)
            row++;
        else if(matrix[row][col] > target)
            col--;
        else
            return true;
    }
    return false;
}

3.删除排序数组反复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

public int removeDuplicates(int[] nums) {
        // 应用双指针
        if(nums==null || nums.length == 1){
            return nums.length;
        }
        int i = 0,j =1;
        while(j<nums.length){
            if(nums[i]==nums[j]){
                j++;
            }else{
                i++;
                nums[i]=nums[j];
                j++;
            }
        }
        return i+1;
    }

4.链表的两头节点

https://leetcode-cn.com/problems/middle-of-the-linked-list/

public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while (q != null && q.next != null) {
            q = q.next.next;
            p = p.next;
        }
        return p;
}

5.爱生气的书店老板

https://leetcode-cn.com/problems/grumpy-bookstore-owner/

/*
首先 找到不扭转的时候客人就称心的数量和 同时更新数组
这样问题就转变为 求数组指定长度最大和的问题
工夫复杂度 O(n) 空间复杂度为O（1）
*/
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int x) {
        int sum = 0, len = customers.length;
        for (int i = 0; i < len; i++) {
            if (grumpy[i] == 0){
                sum += customers[i];
                customers[i] = 0;
            } 
        }
        int num = customers[0];
        int maxval = customers[0];
        for (int i = 1; i < len; i++){
            if (i < x) num = num + customers[i];
            else num = num + customers[i] - customers[i - x];
            maxval = Math.max(maxval, num);
        }
        
        return (sum + maxval);
    }
}

6.滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

/*
  思路： 遍历数组 L R 为滑窗左右边界 只增不减
        双向队列保留以后窗口中最大的值的数组下标 双向队列中的数从大到小排序，
        新进来的数如果大于等于队列中的数 则将这些数弹出 再增加
        当R-L+1=k 时 滑窗大小确定 每次R前进一步L也前进一步 保障此时滑窗中最大值的
        数组下标在[L，R]中，并将以后最大值记录
  举例： nums[1，3，-1，-3，5，3，6，7] k=3
     1：L=0，R=0，队列【0】 R-L+1 < k
            队列代表值【1】
     2: L=0,R=1, 队列【1】 R-L+1 < k
            队列代表值【3】
     解释：以后数为3 队列中的数为【1】 要保障队列中的数从大到小 弹出1 退出3
          但队列中保留的是值对应的数组下标 所以队列为【1】 窗口长度为2 不增加记录
     3: L=0,R=2, 队列【1，2】 R-L+1 = k ,result={3}
            队列代表值【3，-1】
     解释：以后数为-1 队列中的数为【3】 比队列尾值小 间接退出 队列为【3，-1】
          窗口长度为3 增加记录记录为队首元素对应的值 result[0]=3
     4: L=1,R=3, 队列【1，2，3】 R-L+1 = k ,result={3，3}
            队列代表值【3，-1,-3】
     解释：以后数为-3 队列中的数为【3，-1】 比队列尾值小 间接退出 队列为【3，-1，-3】
          窗口长度为4 要保障窗口大小为3 L+1=1 此时队首元素下标为1 没有生效
          增加记录记录为队首元素对应的值 result[1]=3
     5: L=2,R=4, 队列【4】 R-L+1 = k ,result={3，3，5}
            队列代表值【5】
     解释：以后数为5 队列中的数为【3，-1，-3】 保障从大到小 顺次弹出增加 队列为【5】
          窗口长度为4 要保障窗口大小为3 L+1=2 此时队首元素下标为4 没有生效
          增加记录记录为队首元素对应的值 result[2]=5
    顺次类推 如果队首元素小于L阐明此时值生效 须要弹出
*/
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null||nums.length<2) return nums;
        // 双向队列 保留以后窗口最大值的数组地位 保障队列中数组地位的数按从大到小排序
        LinkedList<Integer> list = new LinkedList();
        // 后果数组
        int[] result = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            // 保障从大到小 如果后面数小 弹出
            while(!list.isEmpty()&&nums[list.peekLast()]<=nums[i]){
                list.pollLast();
            }
            // 增加以后值对应的数组下标
            list.addLast(i);
            // 初始化窗口 等到窗口长度为k时 下次挪动在删除过期数值
            if(list.peek()<=i-k){
                list.poll();   
            } 
            // 窗口长度为k时 再保留以后窗口中最大值
            if(i-k+1>=0){
                result[i-k+1] = nums[list.peek()];
            }
        }
        return result;
    }
}

吴邪，小三爷，混迹于后盾，大数据，人工智能畛域的小菜鸟。
更多请关注