高效制胜题解记录

最新推荐文章于 2025-04-17 17:06:00 发布

学习中的owl

最新推荐文章于 2025-04-17 17:06:00 发布

阅读量338

点赞数

分类专栏： java笔记文章标签：算法 leetcode 数据结构

本文链接：https://blog.csdn.net/white1148/article/details/120804530

版权

java笔记专栏收录该内容

33 篇文章

订阅专栏

这篇博客记录了作者在高效制胜LeetCode挑战过程中的解题心得，涵盖从双指针技巧到动态规划策略的应用。文章详细介绍了包括两数之和、三数之和、斐波那契数、爬楼梯等问题的多种解决方案，如二分查找、双指针、动态规划等，并分析了不同方法的时间和空间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

高效制胜

day01 `求和问题`

T1 1. 两数之和 `数组` `哈希表`

方1：遍历

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            //由于前i位已经互相匹配，j从i+1位开始不会遗漏
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0]; //空整型数组
    }
}

方2：hashMap

方法	描述
containsKey()	检查 hashMap 中是否存在指定的 key 对应的映射关系。
containsValue()	检查 hashMap 中是否存在指定的 value 对应的映射关系。
get()	获取指定 key 对应对 value

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //键是 nums[i] 值是i
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            //target-nums[i] map中包含目标值
            //可以避免二次循环
            if(map.containsKey(target-nums[i])){
                return new int[]{i,map.get(target-nums[i])};
            }
            map.put(nums[i],i);
        }
        return new int[0]; 
    }
}

T2 167. 两数之和 II - 输入有序数组

非递减顺序排列 就想到了二分

返回值的顺序是一定的不能用hashMap

方1：二分自己想的

二分模板

int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;
    // 如果这里是 int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
    // 1、下面循环的条件则是 while(left < right)
    // 2、循环内当 array[middle] > value 的时候，right = middle

    while (left <= right)  // 循环条件，适时而变
    {
        int middle = left + ((right - left) >> 1);  // 防止溢出，移位也更高效。同时，每次循环都需要更新。
        if (array[middle] > value)
            right = middle - 1;
        else if (array[middle] < value)
            left = middle + 1;
        else
            return middle;
        // 可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多
        // 如果每次循环都判断一下是否相等，将耗费时间
    }
  
    return -1;
}

题解

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int temp,res;
        for(int i=0;i<nums.length;i++){
            temp = target-nums[i];
            //一个数只能用一次，因为是非递减顺序排列所以有个相等的一定挨在一起(同时包含不相等但相加符合目标的情况)
            if((i+1)<nums.length && nums[i]+nums[i+1]==target) 
            return new int[]{i+1,i+2}; //因为是返回从1开始对下标处理
            //非相等或邻近符合目标
            //使用二分法快速查找目标值
            res = BinarySearch(nums,i,nums.length-1,temp);
            if(res != -1){
                return new int[]{i+1,res+1};
            }
        }
        return new int[0];
    }

    public int BinarySearch(int[] nums,int left,int right,int target){
        int mid;
        while(left <= right){
            mid = left + ((right-left) >>1); //右移1位 比除2快
            if(nums[mid] > target) 
                right = mid - 1;
            else if(nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }

        return -1;
    }
}

方二： 双指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int low = 0,high = nums.length - 1,sum;
        //双指针
        while(low<=high){
            sum = nums[low]+nums[high];
            if(sum == target)
                return new int[]{low+1,high+1};
            //因为是非递减顺序排列
            //比目标大，右指针左移 ；比目标小，左指针右移
            if(sum<target) low++;
            if(sum>target) high--;
        }
        return new int[0];
    }
}

day02 `求和问题`

T1 15. 三数之和

排序 + 双指针 本题的难点在于如何去除重复解

暴力的话3重循环，时空开销大官解想到双指针的过程很精妙

二重和三重可以是并列的，由此想到了双指针

特判，对于数组长度 n，如果数组为 null或者数组长度小于 3，返回 []。
对数组进行排序。
遍历排序后数组

若 nums[i]>0：因为已经排序好(小到大)，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解如[-3,0,2,2,2,3]
令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
- 当 nums[i]+nums[L]+nums[R]=0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
- 若和大于 0，说明 nums[R] 太大，R左移
- 若和小于 0，说明 nums[L]太小，L 右移

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        //数组为空或者长度小于3不会有结果
        if(nums==null && nums.length < 3) return res;
        
        //数组排序
        Arrays.sort(nums); //小到大排序
        int left,right,tmp,len = nums.length; //左右边界，三数和
        
        //遍历排序后的数组
        for(int i=0; i<len; i++){
            //对于小到大的数组当前指大于0，后面不可能有解了
            if(nums[i] >0) return res; 
            
            //跳过重复的数字
            if(i>0 && nums[i] == nums[i-1]) continue;

            left = i+1;
            right = len-1; //边界初始化
            while(left < right){
                tmp = nums[i]+nums[left]+nums[right]; //三数和
                if(tmp == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);

                    res.add(list); 

                    //跳过重复元素
                    while(left<right && nums[left+1]==nums[left]) left++;
                    while(left<right && nums[right-1]==nums[right]) right--;

                    //边界改变继续求值
                    left++;
                    right--;
                }else if(tmp <0){
                    //比0小左边界右移
                    left++;
                }else{
                    //比0大,右边界左移
                    right--;   
                }
            }
        }

        return res;
    }
}

T2 18. 四数之和

暴力4重循环，和三数之和一样最后两重简化成双指针即n-2重循环+双指针

官解 排序+双指针

具体实现时，还可以进行一些剪枝操作：

在确定第一个数之后，如果 nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target

说明此时剩下的三个数无论取什么，四数之和一定大于target，因此退出第一重循环；

在确定第一个数之后，如果

nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target

说明此时剩下的三个数无论取什么，四数之和一定小于 target因此第一重循环直接进入下一轮，枚举 nums[i+1]

在确定前两个数之后，如果

nums[i]+nums[j]+nums[j+1]+nums[j+2] > target

说明此时剩下的两个数无论取什么，四数之和一定大于 target，因此退出第二重循环；

在确定前两个数之后，如果

nums[i]+nums[j]+nums[n-2]+nums[n-1] < target

说明此时剩下的两个数无论取什么值，四数之和一定小target，因此第二重循环直接进入下一轮，枚举 nums[j+1]。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        //特例处理
        if(nums == null || nums.length<4) return res; //空数组或者长度构不成答案返回空
        Arrays.sort(nums); //数组排序

        int left,right,len = nums.length,sum;

        for(int i=0;i<len-3;i++){
            //去掉重复值
            if(i>0 && nums[i]==nums[i-1]) continue;
            //确定一个数的剪枝
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
            if(nums[i]+nums[len-3]+nums[len-2]+nums[len-1] < target) continue;

            for(int j=i+1;j<len-2;j++){
                //去掉重复
                if(j>i+1 && nums[j]==nums[j-1]) continue;
                //确定二个数的剪枝
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2] > target) break;
                if(nums[i]+nums[j]+nums[len-2]+nums[len-1] < target) continue;

                //初始化边界值
                left = j+1;
                right = len-1;

                //双指针
                while(left < right){
                    sum = nums[i]+nums[j]+nums[left]+nums[right];

                    if(sum == target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right])); //合法解加入结果集
                        //边界重复值处理
                        while(left<right && nums[left]==nums[left+1]) left++;
                        while(left<right && nums[right]==nums[right-1]) right--;
                        //边界同时改变
                        left++;
                        right--;
                    }else if(sum <target){
                        //比目标小，右移左边界
                        left++;
                    }else{
                        //比目标大，左移右边界
                        right--;
                    }
                }
            }
        }

        return res;
    }
}

day03 `斐波拉契数列`

T1 509. 斐波那契数

递归暴力

终止条件	f(0)=0,f(1)=1
递归方程	f(n) = f(n-1)+f(n-2)

class Solution {
    public int fib(int n) {
        if(n==0) return 0; //终止条件
        if(n==1) return 1;
        return fib(n-1)+fib(n-2);
    }
}

时间复杂度大

动态规划详细题解

带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图

动态规划叫做「自底向上」

方一：动态规划

状态转移方程

1 n=1,2

f(n) = f(n-1)+f(n-2) n>2

由于 F(n)只和 F(n-1) 与 F(n-2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)

class Solution {
    public int fib(int n) {
        if(n<2) return n; //终止条件
        int p=0,q=0,r=1;
        for(int i=2 ; i<=n ; i++){
            //滚动数组
            p = q;
            q = r;
            r = p+q;
        }
        return r;
    }
}

方2 矩阵快速幂，方3 通项公式数学方法

T2 70. 爬楼梯

斐波拉契数组用动态规划

初始条件	dp[1]=1,dp[2]=2
动态转移方程	dp[n] = dp[n-1]+dp[n-2]

class Solution {
    public int climbStairs(int n) {
        if(n<2) return n;
        int a=0,b=1,r=1;
        for(int i=2;i<=n;i++){
            //滚动数组
            a = b;
            b = r;
            r = a+b;
        }
        return r;
    }
}

day04 `动态规划`

T1 53. 最大子序和

max{dp[n-1]+nums[i],nums[i]} 自己想到的

方一：动态规划

复杂度

时间复杂度：O(n)O(n)，其中 nn 为 \textit{nums}nums 数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度：O(1)O(1)。我们只需要常数空间存放若干变量。

要求的答案是 max{dp(0) , dp(1) , dp(2) , …dp(i) }

动态转移方程 dp[i] = max{dp[n-1]+nums[i],nums[i]}

class Solution {
    public int maxSubArray(int[] nums) {
        int res=nums[0],tmp=0;
        for(int i=0;i<nums.length;i++){
            tmp = tmp+nums[i] > nums[i] ? tmp+nums[i]:nums[i];
            res = Math.max(res,tmp); //dp[0]...dp[i-1]的最大值是res
        }
        return res;
    }
}

方二：分治

官解线段树

对于一个区间 [l,r]，我们可以维护四个量：

lSum 表示 [l,r] 内以 ll 为左端点的最大子段和
rSum 表示 [l,r]内以 rr 为右端点的最大子段和
mSum 表示 [l,r]内的最大子段和
iSum 表示 [l,r]的区间和

首先最好维护的是iSum，区间 [l,r]的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
对于 [l,r]的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。
对于 [l,r]的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
当计算好上面的三个量之后，就很好计算 [l,r]的 mSum 了。我们可以考虑 [l,r]的 mSum 对应的区间是否跨越 mm——它可能不跨越 mm，也就是说 [l,r]的 mSum 可能是「左子区间」的 mSum 和「右子区间」的 mSum 中的一个；它也可能跨越 mm，可能是「左子区间」的 rSum 和「右子区间」的 lSum 求和。三者取大。

class Solution {
    public int maxSubArray(int[] nums) {
        return getInfo(nums , 0 ,nums.length-1).mSum;
    }

    //存放4种可能的类
    public class Status{
        public int lSum,rSum,mSum,iSum; 
        //构造函数
        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum; //左端点的最大区间和
            this.rSum = rSum; //右端点的最大区间和
            this.mSum = mSum; //最大区间和
            this.iSum = iSum; //区间和
        }
    }

    //分
    public Status getInfo(int[] a, int l, int r){
        if(l==r){
            return new Status(a[l],a[l],a[l],a[l]);
        }
        int m = (l+r) >>1; //左移快与除2
        Status lsub = getInfo(a,l,m);
        Status rsub = getInfo(a,m+1,r);
        return pushUp(a,lsub,rsub);
    }

    //治 维护4个量
    public Status pushUp(int[] a,Status lsub,Status rsub){
        int iSum = lsub.iSum + rsub.iSum;
        int lSum = Math.max(lsub.lSum , lsub.iSum+rsub.lSum);
        int rSum = Math.max(rsub.rSum , rsub.iSum+lsub.rSum);
        int mSum = Math.max( Math.max(lsub.mSum,rsub.mSum)  ,  lsub.rSum+rsub.lSum) ; 

        return new Status(lSum,rSum,mSum,iSum);
    }

}

T2 416. 分割等和子集 `数组` `动态规划`

0-1 背包问题 题解

理解本题的每一个元素只有不选择和选择一次两种方式就能联想到01背包

目标 等价转换：是否可以从输入数组中挑选出一些正整数，使得这些数的和等于整个数组元素的和的一半

nums = [1,4,2,3] ——>true [2,3] 和[1,4] target = 5

	0	1	2	3	4
nums[0] = 1	T	T
nums[1] = 4	T	T	T	T	T
nums[2] = 2	T	T	T
nums[3] = 3	T	T	T	T

空间优化

nums[i]	1	4	2	3
						<—
dp[j]	0	1	2	3	4	5
		T				T

class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0; //存放数组和
        for(int i=0;i<len;i++){
            sum += nums[i];
        }
            
        if(sum % 2 ==1){  //数组和为奇数 不符合分割等和
            return false;
        } 
            
        
        int target = sum/2;
        boolean[] dp = new boolean[target+1];

        dp[0] = true;
        if(nums[0] <= target){    //初始化动态数组
            dp[nums[0]] = true;
        }

        for(int i=1 ; i<len ; i++){
            //倒序防止覆盖
            for(int j=target ; j>=nums[i] ; j--){
                if(dp[target]){
                    return true;
                } 

                dp[j] = dp[j] || dp[j-nums[i]]; // j-nums[i] 是最开始
            }
        }

        return dp[target];
    }
}

T3 322. 零钱兑换

动态规划 F(i) 面值为i消耗硬币的个数 n是面额的种类

F(i)=minF(i−c*j)+1 (j=0…n−1)

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount+1;
        int[] dp = new int[amount+1]; //存放i面额需要的硬币数量
        Arrays.fill(dp,max); //初始化dp数组
        
        dp[0] = 0; //0面额0枚

        for(int i=0 ; i <=amount ; i++){
            for(int j=0 ; j<coins.length ; j++){
                if(coins[j] <= i){ //可能可以组成面额
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1); 
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount] ; //因为初始化max ,最后结果是max说明没有组成方案
    }
}

day05 `堆栈`

T1 20. 有效的括号 `栈` `字符串`

辅助栈法

class Solution {
    public boolean isValid(String s) {
        if(s.length()%2 == 1)  //长度是奇数
            return false;

        //把括号组成对存入map
        HashMap<Character,Character> map = new HashMap<Character,Character>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        
        //链表比Stack节约内存
        Deque<Character> stack = new LinkedList<Character>(); //辅助栈
        for(char c :s.toCharArray()){
            if(map.containsKey(c)){ //右括号判断
                //之前无左括号或者，不是对应的左括号
                if(stack.isEmpty() || stack.peek()!=map.get(c) ){
                    return false;
                }else{
                    stack.pop();
                }
            }else{//左括号入栈
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

T2 496. 下一个更大元素 I `栈` `数组` `哈希表` `单调栈`

方一: 暴力

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int j,k,tmp;
        for(int i=0 ; i<len1 ; i++){
            tmp = nums1[i];
            j=0;
            while(j<len2 && nums2[j] != tmp) j++;
            j++; //nums1[i] == nums2[j]
            
            while(j<len2 && nums2[j] < tmp) j++;
            //nums1[i] < nums2[j]
            
            if(j == len2)
            {
                nums1[i] = -1;
                continue;
            }else{
                nums1[i] = nums2[j];
            }
        }

        return nums1;
    }
}

方二： 单调栈

朴素的单调栈是帮助我们找到左边或者右边「最近」的数

根据题意，数组 nums1 视为询问。我们可以：

先对 nums2 中的每一个元素，求出它的右边第一个更大的元素；
将上一步的对应关系放入哈希表（HashMap）中；
再遍历数组 nums1，根据哈希表找出答案。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        
        Deque<Integer> stack = new ArrayDeque<Integer>(); //单调栈
        HashMap<Integer,Integer> map = new HashMap<>(); // 当前元素，第一个大于当前元素的

        for(int i=0 ; i<len2 ; i++){
            //保证栈内元素单调不增
            while(!stack.isEmpty() && stack.peekLast() < nums2[i]){ //非空时栈底元素小于当前值
                map.put(stack.removeLast(),nums2[i]); //存入大小关系
            }
            stack.addLast(nums2[i]); //加入栈顶
        }
        
        for(int i=0 ; i<len1 ; i++){
            nums1[i] = map.getOrDefault(nums1[i],-1);
        }

        return nums1;
    }
}

T3 456. 132 模式 `栈` `数组` `二分查找` `有序集合` 不懂

方法：单调栈

ijk 132

枚举 i：由于i是 132结构中最小的数，那么相当于我们要从 i 后面，找到一个对数 (j,k)，使得 (j,k)都满足比i大

同时j和k之间存在 j > k的关系。由于我们的遍历是单向的，因此我们可以将问题转化为找 k，首先 k 需要比 i 大，同时在 [i, k] 之间存在比 k 大的数即可。

单调栈维护的是3，max_k维护的是2，枚举的是1，

max_k来源与单调栈: 所以其索引一定大于栈顶的元素，但其值一定小于栈顶元素，故栈顶元素就是3，即找到了对“32”。

于是当出现nums[i] < max_k时，即找到了"12"，这个时候一定会有3个元素的，而栈顶3必定大于2，故也大于1，即满足“132”

class Solution {
    public boolean find132pattern(int[] nums) {
        int len = nums.length;
        Deque<Integer> stake = new ArrayDeque<>();
        int k = Integer.MIN_VALUE; //132种的2 值比栈顶小，索引大于栈顶

        //枚举 132中的1
        for(int i=len-1 ; i >=0 ; i--){
            if(nums[i] < k) return true; // 找到“1” 和 “2” 同时此时必有栈顶“3”

            while(!stake.isEmpty() && stake.peekLast() < nums[i]){ //找到离“1”近且大
                k = Math.max(k,stake.removeLast());
            }

            stake.addLast(nums[i]); //存入栈顶
        }
        return false;
    }
}

day06 `数学`

T1 119. 杨辉三角 II `数组` `动态规划`

官解

第 n 行（从 0开始编号）的数字有 n+1 项
$\mathcal{C}_n^i=\mathcal{C}_{n-1}^i+\mathcal{C}_{n-1}^{i-1}$

class Solution {
    public List<Integer> getRow(int rowIndex) {
        //数组嵌套 每层长度不同 杨辉三角每层是n+1
        List<List<Integer>> list = new ArrayList<List<Integer>>(); 

        for(int i=0 ; i<=rowIndex ; i++){
            List<Integer> row = new ArrayList<Integer>(); //当前行
            for(int j=0 ; j<=i ; j++){ //长度n+1
                if(j==0 || j==i){ //两端是1
                    row.add(1);
                }else{
                    row.add(list.get(i-1).get(j-1)+list.get(i-1).get(j)); //左上角和右上角
                }
            }
            list.add(row); //当前行加入集合
        }

        return list.get(rowIndex);
    }
}

优化版

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add(0);
            for (int j = i; j > 0; --j) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}

T2 279. 完全平方数 `bfs` `数组` `动态规划`

方法： 动态规划

相当于一个金额用最少硬币的变种
$dp[i]=1+j=min(dp[i−j^2]) 其中(j=1....√i)$

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1]; //0到n 所需的个数
        int minNum;
        for(int i=1 ; i<=n ; i++){
            minNum = Integer.MAX_VALUE; //初始化
            for(int j=1 ; j*j<=i ; j++){ //j是可用的完全平方数 1，4，9......   1<=j<=√i
                minNum = Math.min(minNum,dp[i - j*j]);
            }
            dp[i] = minNum+1; //最少的数量加上本次的1个
        }

        return dp[n];
    }
}

T3 483. 最小好进制 `数学` `二分`

二分解法

class Solution {
    /* 数学方法 */
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        // 枚举 k进制 中 1 的个数，最多为 二进制 时的位数
        for (int i = (int) (Math.log(num) / Math.log(2) + 1); i > 2; --i) {
            // k^0 + k^1 + …… + k^(i-1) = n -- 解方程计算 k
            // k < n^(1/(i - 1)) < k +1
            long k = (long) Math.pow(num, 1.0 / (i - 1));
            // 检查 k 进制数 (11…11) (i个1)是否是n
            long res = 0;
            for (int j = 0; j < i; ++j)
                res = res * k + 1;
            if (res == num)
                return Long.toString(k);
        }
        return Long.toString(num - 1);
    }
}

作者：meteordream
链接：https://leetcode-cn.com/problems/smallest-good-base/solution/zui-xiao-hao-jin-zhi-er-fen-shu-xue-fang-frrv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

day07 `树`

T1 112. 路径总和 `树` `DFS` `二叉树`

方一：BFS

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){ //特殊值
            return false;
        }

        
        Queue<TreeNode> nodes = new LinkedList<TreeNode>(); //节点队列
        Queue<Integer>   node_vals = new LinkedList<Integer>(); //到当前节点对应的和
        
        //初始化
        nodes.offer(root); //加入根
        node_vals.offer(root.val);
        TreeNode tmp;
        int sum;

        while(!nodes.isEmpty()){ //BFS 层序遍历
            tmp = nodes.poll();
            sum = node_vals.poll();

            if(tmp.left==null && tmp.right==null){ //当前分支结束
                if(sum == targetSum){ //符合要求
                    return true; 
                }
                continue;
            }

            //叶子节点 有值
            if(tmp.left != null){
                nodes.offer(tmp.left);
                node_vals.offer(tmp.left.val+sum);
            }
            if(tmp.right != null){
                nodes.offer(tmp.right);
                node_vals.offer(tmp.right.val+sum);
            }
        }
        return false;

    }
}

方二：递归剪枝的DFS

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;  
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T2 二叉搜索树中第K小的元素 `树` `DFS` `二叉搜索树`

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树

中序遍历序列左根右，第 k-1 个元素就是第 k 小的元素

方一：递归

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> res = indoor(root, new ArrayList<Integer>());
        return res.get(k-1); //先序遍历 第k-1个就是目标
    }

    //中序遍历 左根右
    public ArrayList<Integer> indoor(TreeNode node , ArrayList<Integer> list){
        if(node == null) return list; //当前节点无叶子
        indoor(node.left , list);
        list.add(node.val);
        indoor(node.right , list);
        return list; 
    }
}

方二：迭代

栈的帮助下，可以将方法一的递归转换为迭代

class Solution {
  public int kthSmallest(TreeNode root, int k) {
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

    while (true) {
      while (root != null) {
        stack.add(root);
        root = root.left;
      }
      root = stack.removeLast();
      if (--k == 0) return root.val;
      root = root.right;
    }
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/solution/er-cha-sou-suo-shu-zhong-di-kxiao-de-yuan-su-by-le/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T3 968. 监控二叉树 `树` `DFS` `动态规划`

官解

根据上面的讨论，能够分析出，对于每个节点root ，需要维护三种类型的状态：

状态 a：root 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
状态 b：覆盖整棵树需要的摄像头数目，无论root 是否放置摄像头。
状态 c：覆盖两棵子树需要的摄像头数目，无论节点root本身是否被监控到。
根据它们的定义，一定有 a≥b≥c。

左右孩子 left*,right 对应的状态变量分别为 (L_a,L_b,L_c) ,以及 (R_a,R_b,R_c)

a = L_c + R_c + 1
b=min(a , min(L_a+R_b , R_a+L_b))
对于 c 而言，要保证两棵子树被完全覆盖，要么root 处放置一个摄像头，需要的摄像头数目为 a；要么 root 处不放置摄像头，此时两棵子树分别保证自己被覆盖，需要的摄像头数目为 L_b+R_b即

c = min(a , L_a+L_b)

方法一：动态规划

class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = dfs(root); //数组维护的是a,b,c
        return res[1]; //返回b
    }

    //深度优先搜索 递归
    public int[] dfs(TreeNode node){
        if(node == null){
            return new int[]{Integer.MAX_VALUE/2 , 0 , 0}; // 递归终止
        }
        int[] leftArray = dfs(node.left);
        int[] rightArray = dfs(node.right);
        int[] array = new int[3]; //当前节点的 abc
        array[0] = leftArray[2] + rightArray[2]+1; //a
        array[1] = Math.min(array[0] , Math.min(leftArray[0]+rightArray[1] , leftArray[1]+rightArray[0])); //b
        array[2] = Math.min(array[0] , leftArray[1]+rightArray[1]);

        return array;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-cameras/solution/jian-kong-er-cha-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

day08 `字符串`

T1 720. 词典中最长的单词 `字典树` `数组` `哈希表` `字符串`

前缀树模板

class Trie {

    private boolean isEnd;  // 是否为结束字符
    private Trie[] next;    // 下一个字符

    public Trie() {
        isEnd = false;
        next = new Trie[26];
    }

    public void insert(String word) {
        // 从第一个节点开始，可以想象成一个空节点
        Trie cur = this;
        int len = word.length();
        for (int i = 0; i < len; i++) {
            char ch = word.charAt(i);
            // 如果当前节点的下一个字符处还没有开辟，那就新创建一个
            if (cur.next[ch-'a'] == null) 
                cur.next[ch-'a'] = new Trie();
            // 节点指针后移
            cur = cur.next[ch-'a'];
        }
        // 循环结束，当前节点指向的字符为结束字符
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Trie cur = prefixSearch(word);
        // 字符全部匹配，且最后一个字符为结束字符
        return cur != null && cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        // 字符全部匹配
        return prefixSearch(prefix) != null;
    }

    // 方法抽取，复用重复代码
    private Trie prefixSearch(String word) {
        Trie cur = this;
        int len = word.length();
        for (int i = 0; i < len; i++) {
            char ch = word.charAt(i);
            // 如果当前节点的对应字符处尚未开辟，说明没有对应的word插入
            if (cur.next[ch-'a'] == null) return null;
            cur = cur.next[ch-'a'];
        }
        return cur;
    }
}

本题题解

方法：前缀树+dfs搜索

dfs搜索时并不是简单地一直往下搜索，而是要求在连续单词结尾的节点进行深度搜索

在 java 中，我们使用了更通用的面向对象方法

class Trie{ //前缀树
    Trie[] children;
    boolean isEnd; //是否是结尾节点
    String word; //用来保存当前遍历的word

    public Trie(){
        children = new Trie[26];
        isEnd = false;
    }
}
class Solution {
    Trie root = new Trie(); //类变量 创建一个前缀树
    private int maxLen = 0; 
    private String res = "";

    public String longestWord(String[] words) {
        
        for(String word : words){
            insert(word); //当前词放入前缀树
        }

        getMaxLengthWord(root,0); //寻找目标

        return res;
    }

    //当前词放入前缀树
    public void insert(String word){
        int n = word.length();
        Trie node = this.root;
        char c;
        for(int i=0 ; i<n ; i++){
            c = word.charAt(i);

            if(node.children[c-'a'] == null){ //当前字符不存在与前缀树树中
                node.children[c-'a'] = new Trie();
            }

            node = node.children[c-'a']; //节点后移
        }

        node.isEnd = true; //当前单词结束 标记末尾，记录单词
        node.word = word;
    }

    // 通过递归遍历 node 的 children 数组并且每遍历一次深度 deep 增加 1
    public void getMaxLengthWord(Trie node , int deep){

        if(deep > 0 && !node.isEnd) return ; //当前节点不是初始节点不是结尾，不可能构成字典

        if(deep > maxLen){ //当前深度大于最大长度
            res = node.word;
            maxLen = deep;
        }

        for(int i=0 ; i<node.children.length; i++){
            if(node.children[i] != null){
                getMaxLengthWord(node.children[i] , deep+1);
            }
        }
    }
}

作者：Booooo_
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary/solution/ci-dian-zhong-zui-chang-de-dan-ci-zi-dia-2ud2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T2 3. 无重复字符的最长子串 `哈希表` `字符串` `滑动窗口`

方法 滑动窗口

假设我们选择字符串中的第 kk 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r_k

那么当我们选择第 k+1个字符作为起始位置时，首先从 k+1到 r_k的字符显然是不重复的，

并且由于少了原本的第 k 个字符，我们可以尝试继续增大 r_k，直到右侧出现了重复字符为止

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<Character>(); //存放字符判断是否有重复
        int len = s.length();
        int now = -1 , res = 0; //now是子串移动指针，res最长子串

        for(int i=0 ; i<len ; i++){
            if(i != 0){ //每次右移开始新的字串
                set.remove(s.charAt(i -1));
            }

            while(now+1<len &&  !set.contains(s.charAt(now+1))){ //直到重复跳出
                set.add(s.charAt(now+1)); //无重复存入数组
                now++;
            }

            res = Math.max(res , now-i+1); //now-i+1当前字串的长度
        }

        return res;
    }
}

T3 97. 交错字符串 `字符串` `动态规划`

动态规划+滚动数组

f(i,j) = [f(i−1,j) && s1(i−1) = s3 §] || [f(i,j−1) && s2(j−1)=s3§]

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n=s1.length() , m=s2.length() , t = s3.length(),p; //数组的长度 p存放当前两字串和

        if(n+m != t) return false; //字串和不等于目标字串不可能是交错字符串

        boolean[] dp = new boolean[m+1]; //因为i只和i-1有关，滚动数组简化 dp变为一维

        dp[0] = true;
        for(int i=0 ; i<=n ; i++){
            for(int j=0 ; j<=m ; j++){
                
                p = i+j -1; //p指向s3字串的上一位
                if(i > 0){
                    //[f(i−1,j) && s1(i−1) = s3 (p)]
                    dp[j] = dp[j] && (s1.charAt(i-1) == s3.charAt(p)); 
                }

                if(j > 0){
                    // [i>0的if判断] || [f(i,j−1) && s2(j−1)=s3(p)]
                    dp[j] = dp[j] || (dp[j-1] && s2.charAt(j-1) == s3.charAt(p));
                }
            }
        } 

        return dp[m];
    }
}

day 09 `字符串搜索`

T1 28. 实现 strStr() `双指针` `字符串` `字符串匹配`

双指针

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length() , m=needle.length();
        
        boolean flag ; //是否匹配的标识
        for(int i=0; i+m <=n ; i++){
            flag = true;
            for(int j=0 ; j<m ; j++){
                if(haystack.charAt(i+j) != needle.charAt(j)){ //i是本次匹配开始位置
                    flag = false;
                }
            }
            if(flag){
                return i;
            }
        }

        return -1;
    }
}

T2 524. 通过删除字母匹配到字典里最长单词 `数组` `双指针` `字符串`

无忧化的双指针

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String res = ""; //结果字符串
        int i,j; //i是遍历dic单词的指针，j是目标s的指针

        for(String str: dictionary){
            i=0;
            j=0;
            while(i<str.length() && j<s.length()){
                if(str.charAt(i) == s.charAt(j)){
                    i++;
                }
                j++; //目标字串始终移动
            }

            if(i == str.length()){ //说明目标字符串等于当前字符串
                //当前字符串长度大于res长度 或者 (res和当前字串成都相等时，当前字串字典序小于res)
                if(res.length()< str.length() || (res.length()==str.length() && str.compareTo(res)<0)){
                    res = str;
                }
            }
        }

        return res;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/solution/tong-guo-shan-chu-zi-mu-pi-pei-dao-zi-di-at66/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T3 1392. 最长快乐前缀 `字符串` `字符串匹配` `哈希函数` 不会

kmp

class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        int[] fail = new int[n];

        Arrays.fill(fail, -1);

        for(int i=1 ; i<n ; i++){
            int j = fail[i-1];

            while(j!=-1 && s.charAt(j+1)!=s.charAt(i)){
                j = fail[j];
            }

            if(s.charAt(j+1) == s.charAt(i)){
                fail[i] = j+1;
            }
        }

        return s.substring(0, fail[n-1]+1);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-happy-prefix/solution/zui-chang-kuai-le-qian-zhui-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

day10 `图`

T1 1042. 不邻接植花 `DFS` `BFS`

染色法

限制每个节点的度为3，同时提供四种颜色，因此不需要回溯

存储邻接点信息
遍历所有节点，对于每个节点
- 查看其邻接点颜色，使用不同的颜色染色即可

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        Map<Integer, Set<Integer>> graph = new HashMap<>(); //key是花园 value是花园连同的其他花园
        for(int i=0 ; i<n ; i++){
            graph.put(i,new HashSet<>()); //图初始化
        }

        //图的构建
        for(int[] path: paths){ 
            int a = path[0] - 1;
            int b = path[1] - 1;
            graph.get(a).add(b); //双向通路
            graph.get(b).add(a);
        }
        
        int[] res = new int[n]; //结果数组 使用过的花

        for(int i=0 ; i<n ; i++){
            boolean[] used = new boolean[5]; //4种花的使用情况

            for(int adj : graph.get(i)){ //i花园相邻的花园集合
                used[res[adj]] = true;
            }

            for(int j=1 ; j<=4 ; j++){ //种花
                if(!used[j]){
                    res[i] = j;
                }
            }
        }

        return res;
    }
}

作者：Jiachen_Zhang
链接：https://leetcode-cn.com/problems/flower-planting-with-no-adjacent/solution/jian-dan-de-ran-se-wen-ti-bu-xu-yao-kao-lu-hui-su-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T2 787. K 站中转内最便宜的航班 `DFS` `BFS`

bellman-ford 动态规划

(j,i)∈flights f[t][i] 表示通过恰好 t 次航班，从出发城市 src 到达城市 i 需要的最小花费
$f[t][i]= min{f[t−1][j]+cost(j,i)}$
最多只能中转 k次，也就是最多搭乘 k+1次航班

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = 10000*101+1; //根据题意得到的最大值
        int[][] dp  = new int[k+2][n]; //最多k+1趟

        for(int i=0 ; i<=k+1 ; i++){ //动态数组初始化
            Arrays.fill(dp[i] ,INF);
        }

        dp[0][src] = 0; //出发点到出发点无花费
        int i, j , cost;
        for(int t=1 ; t<=k+1 ; t++){
            for(int[] flight : flights){
                j=flight[0]; i=flight[1]; cost=flight[2];
                //恰好 t 次航班，从出发城市 src 到达城市 i 需要的最小花费
                dp[t][i] = Math.min(dp[t][i] , dp[t-1][j]+cost);
            }
        }

        int res = INF;
        for(int t=1 ; t<=k+1 ;t++){
            res = Math.min(res, dp[t][dst]);
        }

        return res == INF ? -1:res; //结果是最大值说明没有路径
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/solution/k-zhan-zhong-zhuan-nei-zui-bian-yi-de-ha-abzi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

day11 `图`

T1 79. 单词搜索 `数组` `回溯` `矩阵`

方法：回溯

class Solution {
    public boolean exist(char[][] board, String word) {
        int n = board.length, m = board[0].length;
        boolean[][] visted = new boolean[n][m]; //标记是否走过

        boolean flag;
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<m ;j++){
                flag = find(board , visted , i , j , word,0); //从board[i][j]开始回溯查找
                if(flag) return true; 
            }
        }
        return false;
    }


    public boolean find(char[][] board , boolean[][] visted , int i ,int j , String word ,int k){
        if(board[i][j] != word.charAt(k)){ //当前格子字符 和 目标字符串k位不相等
            return false;
        }else if(k+1 == word.length()){ //当前位相等 且加上该位后就是word
            return true;
        }

        visted[i][j] = true;
        //当前位 等于 目标k位  查看上下左右是否符合 word的k+1位
        boolean res = false;
        int newi , newj;
        int[][] direction = new int[][]{ {0,1} , {0,-1} , {1,0} , {-1,0}}; //上下左右坐标变化值
        for(int[] dir : direction){ //遍历4个方向
            newi = i+dir[0]; newj = j+dir[1];

            if(newi>=0 && newi < board.length   &&   newj>=0 && newj<board[0].length){ //新坐标没有越界
                if(!visted[newi][newj]){
                    res = find(board , visted , newi , newj , word ,k+1);
                    if(res){
                        break;
                    }
                }
            }
        }

        visted[i][j] = false; //标志该格已遍历
        return res;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T2 329. 矩阵中的最长递增路径 `DFS` `BFS`

方法：备忘录+dfs

如果相邻的两个单元格的值不相等，则在相邻的两个单元格之间存在一条从较小值指向较大值的有向边。问题转化成在有向图中寻找最长路径

由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。用矩阵memo 作为缓存矩阵，已经计算过的单元格的结果存储到缓存矩阵中

class Solution {

    int[][] dirction = new int[][]{ {0,1} , {0,-1} , {1,0} , {-1,0}}; //上下左右坐标变化值
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length==0 || matrix[0].length==0){ //null || {} || {{}}
            return 0;
        }
        int n = matrix.length , m = matrix[0].length;
        int[][] memo = new int[n][m]; //memo备忘录记录每格的最长路径
        int res =0;
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<m ; j++){
                res = Math.max(res , dfs(matrix , memo , i , j)); //找到最大的值
            }
        }
        return res;
    }

    //备忘录+dfs
    public int dfs(int[][] matrix , int[][] memo , int i ,int j){
        if(memo[i][j] !=0){
            return memo[i][j]; //返回记录值
        }
        memo[i][j]++; //自身+1

        int newi,newj;
        for(int[] dir : dirction){ //上下左右
            newi = i+dir[0]; newj = j+dir[1];
            //不越界同时保证递增
            if(newi>=0 && newi<matrix.length && newj>=0 && newj<matrix[0].length  && matrix[newi][newj] > matrix[i][j] ){
                memo[i][j] = Math.max(memo[i][j] , dfs(matrix , memo , newi ,newj)+1);
            }
        }

        return memo[i][j];

    }
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/ju-zhen-zhong-de-zui-chang-di-zeng-lu-jing-by-le-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

day12 `动态规划`

T1 121. 买卖股票的最佳时机 `数组` `动态规划`

max(prices[j] - prices[i])

class Solution {
    public int maxProfit(int[] prices) {
        int maxpro=0, minPrice = Integer.MAX_VALUE; //最大利润 ， 最低价格

        for(int i=0 ; i < prices.length ; i++){
            if(prices[i] < minPrice){ //比历史最低低，更新
                minPrice = prices[i];
            }else if(prices[i] - minPrice > maxpro){ //当前价格-史低 > 最大利润
                maxpro = prices[i] - minPrice;
            }
        }

        return maxpro;
    }
}

T2 122. 买卖股票的最佳时机 II `贪心` `数组` `动态规划`

贪心：只在连续上涨的时候购买

等价于每天都买卖

class Solution {
    public int maxProfit(int[] prices) {
        int maxpro = 0 , tmp; //最大利润，当前利润

        for(int i=1 ; i<prices.length ; i++){
            tmp = prices[i] - prices[i-1];
            if(tmp > 0){ //只在连续上涨的时候购买
                maxpro += tmp;
            }
        } 
        return maxpro;
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/best-time-to-buy-and-sell-stock-ii-zhuan-hua-fa-ji/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

day13 数组

T1 218. 天际线问题 `树状数组` `线段树` `数组`

方法：扫描线&优先队列

扫描线的核心在于 将不规则的形状按照水平或者垂直的方式，划分成若干个规则的矩形。

左端点：因为是左端点，必然存在一条从右延展的边，但不一定是需要被记录的边，因为在同一矩形中，我们只需要记录最上边的边。这时候可以将高度进行入队；

右端点：此时意味着之前某一条往右延展的线结束了，这时候需要将高度出队（代表这结束的线不被考虑）。

java lambada

//接受2个参数(数字),并返回他们的差值  
(x, y) -> x – y

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>(); //结果数组

        //预处理所有的点,左端点 高度为负，右端点高度为正
        List<int[]> points = new ArrayList<>();
        int left,right,high;
        for(int[] build : buildings){
            left = build[0] ; right = build[1] ; high = build[2];
            points.add(new int[]{left , -high});
            points.add(new int[]{right , high});
        }

        // 先按照横坐标进行排序
        // 如果横坐标相同，则按照左端点排序
        // 如果相同的左/右端点，则按照高度进行排序
        Collections.sort(points , (a,b)->{
            if(a[0] != b[0]) return a[0] - b[0];
            return a[1] -b[1];
        });

        //大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->b-a);
        int prev=0 , cur , point , height;
        queue.add(prev);
        for(int[] p : points){
            point = p[0] ; height = p[1];
            if(height < 0){ //左端点，高度入队
                queue.add(-height);
            }else{ //右端点, 说明这条边结束当前高度出队
                queue.remove(height);
            }

            cur = queue.peek();
            if(cur != prev){ //高度改变，当前横坐标高度存入结果集
                List<Integer> list = new ArrayList<>();
                list.add(point);
                list.add(cur);

                res.add(list);
                prev = cur;
            }
        } 
        return res;
    }
}

作者：AC_OIer
链接：https://leetcode-cn.com/problems/the-skyline-problem/solution/gong-shui-san-xie-sao-miao-xian-suan-fa-0z6xc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T2 807. 保持城市天际线 `贪心` `数组` `矩阵`

顶到底方向是数组每列的最大值

左到右方向是数组每行的最大值

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int len = grid.length;
        int[] rowMaxNums = new int[len]; //顶到底
        int[] colMaxNums = new int[len]; //左到右

        //得到天际线数组
        for(int i=0 ; i<len ; i++){
            for(int j=0 ; j<len ;j++){
                rowMaxNums[i] = Math.max(rowMaxNums[i] , grid[i][j]);
                colMaxNums[j] = Math.max(colMaxNums[j] , grid[i][j]);
            }
        }

        //计算天际线的和
        int res=0;
        for(int i=0 ; i<len ; i++){
            for(int j=0 ; j<len ; j++){
                res += (Math.min(rowMaxNums[i] , colMaxNums[j]) - grid[i][j]);
            }
        }
        return res;
    }
}

day14 `双指针`

T1 11. 盛最多水的容器 `贪心` `数组` `双指针`

方法：双指针

S(i , j) = min(h[i] , h[j]) * (j-i)

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1变短：

若向内移动短板，水槽的短板 min(h[i] , h[j]) 可能变大，因此下个水槽的面积 可能增大 。
若向内移动长板，水槽的短板 min(h[i] , h[j]) 不变或变小，因此下个水槽的面积 一定变小

class Solution {
    public int maxArea(int[] height) {
        int i=0 ,j = height.length-1 , res = 0; //i指向头 j指向尾
        while(i < j){
            res = height[i] < height[j] ?
                    Math.max(res , (j-i) * height[i++]): //短板是i i++ 先操作后加1
                    Math.max(res , (j-i) * height[j--]);
        }

        return res;
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

T2 42. 接雨水 `栈` `数组` `双指针` `动态规划`

方法：动态规划

显然，除了leftMax[0] = height[0] , rightMax[n-1] = height[n-1]

当 1<= i <= n-1时， leftMax[i] = max( leftMax[i-1] , height[i]);
当 0<= i <= n-2时， leftMax[i] = max( leftMax[i+1] , height[i]);

对于 0<= i < n，下标 i处能接的雨水量等于

min(leftMax[i] , rightMax[i]) - height[i]

class Solution {
    public int trap(int[] height) {
        int len = height.length ; 

        if(len == 0) return 0; //特殊值处理

        //计算左高边数组
        int[] leftMax = new int[len];
        leftMax[0] = height[0]; //初始化
        for(int i=1 ; i< len ; i++){
            leftMax[i] = Math.max( leftMax[i-1] , height[i]);
        }

        //计算右高边数组
        int[] rightMax = new int[len];
        rightMax[len-1] = height[len-1];
        for(int i=len-2 ; i>=0 ; i--){
            rightMax[i] = Math.max(rightMax[i+1] , height[i]);
        }

        //计算雨水面积
        int res = 0;
        for(int i=0 ; i<len ; i++){
            res += Math.min(leftMax[i] , rightMax[i]) - height[i];
        }

        return res;

    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。