一、快慢指针

移除元素问题  
    int[] arr = {0, 1, 2, 2, 3, 0, 4, 2};
        // 2. 定义一个变量表示要删除的数据
    int val = 2;

        // 3. 利用快慢指针去删除数据
    int slow = 0;
    int fast = 0;

    while (fast < arr.length){
            // 4. 判断当前快指针指向的元素是否为2
        if(arr[fast] != val){
            // 不相等
            // 如果快指针当前的位置不是2,那么就把这个数字存入到慢指针的位置, 慢指针,快指针往后移动一位
            rr[slow] = arr[fast];
            slow++;
        }
        fast++;
    }

二、二路归并

package com.itheima.test;

public class Test3 {
    public static void main(String[] args) {
        /*
            给定两个正序数组arr1和arr2，请先合并数组，并找出合并之后数组的中位数。
            举例：
            1 2 3 4 5 6 7 8 9       中位数：5
            1 2 3 4 5 6            中位数： （ 3 + 4 ） / 2
        */

        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = {2,3,4,5,6};
        double res = findMedianSortedArrays(arr1, arr2);
        System.out.println(res);
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        int[] arr = new int[len];
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < len; i++) {
            if(index1 == len1){
                arr[i] = nums2[index2];
                index2++;
                continue;
            }
            if(index2 == len2){
                arr[i] = nums1[index1];
                index1++;
                continue;
            }
            if(nums1[index1] < nums2[index2]){
                arr[i] = nums1[index1];
                index1++;
            }else{
                arr[i] = nums2[index2];
                index2++;
            }
        }

        if(len % 2 == 0){
            double num1 = arr[len / 2 - 1];
            double num2 = arr[len / 2];
            return (num1 + num2) /2;
        }else{
            //奇数
            //1 2 3 4 5
            //0 1 2 3 4
            return arr[(len - 1) / 2];
        }
    }
}

三、动态规划dp思想

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

既然雨水是否留下看左右的柱子，那么我们就可以把问题拆成两部分，

1. 假设右边有一个无限高的柱子，水无法从右边流走，只能从左边流走。
2. 假设左边有一个无限高的柱子，水无法从左边流走，只能从右边流走。
3. 再计算两个的交集就能得到最终的结果。

package com.itheima.test;

public class Test5 {
    public static void main(String[] args) {
      /*
        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
        输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
        输出：6
        解释：下面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
      */

        // 1. 定义数组
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

        // 2. 从左往右遍历,记录雨水 + 柱子的面积总和
        // 2.1 定义数组记录从左往右看的数据
        int[] leftMax = new int[arr.length];

        // 2.2 定义第三方变量temp，记录当前最高的柱子
        int temp = arr[0];

        // 2.3 遍历数组
        for (int i = 0; i < arr.length; i++) {
            // 判断 temp  数组里面的数据
            if(temp > arr[i]){
                leftMax[i] = temp;
            }else{
                leftMax[i] = arr[i];
                temp = arr[i];
            }
        }

        // 3. 从右往左遍历,记录雨水 + 柱子的面积总和
        int[] rightMax = new int[arr.length];
        temp = arr[arr.length - 1];

        for (int i = arr.length - 1; i >= 0; i--) {
            if(temp > arr[i]){
                rightMax[i] = temp;
            }else{
                rightMax[i] = arr[i];
                temp = arr[i];
            }
        }

        // 4. 取交集
        int[] result = new int[arr.length];

        for (int i = 0; i < rightMax.length; i++) {
            // leftMax[i]: 从左到右数组中的数据
            // rightMax[i]: 从右到左数组中的数据
            if(leftMax[i] < rightMax[i]){
                result[i] = leftMax[i];
            }else{
                result[i] = rightMax[i];
            }
        }

       // 5. 求和
        int sum = 0;
        for (int i = 0; i < result.length; i++) {
            sum = sum + result[i];
        }

        // 6. 去掉柱子的面积
        for (int i = 0; i < arr.length; i++) {
            sum = sum - arr[i];
        }

        System.out.println(sum);
    }
}