42. 接雨水

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

示例 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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

状态：不会，看灵山的视频理解了。链接

前缀和后缀分解

思路：是否可以接水，看前后的大小是否大于该点，如果前后都大于该点则能接水。使用前缀和后缀分解，创建数组pre_max，suf_max，pre_max[i]表示在这个下标及之前最大的值，suf_max[i]表示下标及之后最大的值。则下标位置上接水量取决于前后缀中最小的高度再减去该点的高度。

class Solution {
    public int trap(int[] height) {
        int[] pre_max=new int[height.length];
        int[] suf_max=new int[height.length];
        pre_max[0]=height[0];
        suf_max[height.length-1]=height[height.length-1];
        for(int i=1;i<height.length;i++){
            pre_max[i]=Math.max(pre_max[i-1],height[i]);
        }
        for(int i=height.length-2;i>=0;i--){
            suf_max[i]=Math.max(suf_max[i+1],height[i]);
        }
        int sum=0;
        for(int i=0;i<height.length;i++){
            sum+=(Math.min(pre_max[i],suf_max[i])-height[i]);
        }
        return sum;
    }
}

时间复杂度：O(n)

空间复杂度：O(n) 

双指针

思路：根据上一个思路，我们可以知道这个下标位置接水取决于前后的最大值，所以可以用双指针去优化。木桶定律就是装水的高度取决于最短的木板，所以只要有一边的值打过另一边这个地方就可以装水了，然后移动指针。

class Solution {
    public int trap(int[] height) {
        int pre_max=0;
        int suf_max=0;
        int left=0;
        int right=height.length-1;
        int sum=0;
        while(left<=right){
            pre_max=Math.max(pre_max,height[left]);
            suf_max=Math.max(suf_max,height[right]);
            if(pre_max<suf_max){
                sum+=(pre_max-height[left]);
                left++;
            }else{
                sum+=(suf_max-height[right]);
                right--;
            }
        }
        return sum;   
    }
}

单调队列

还没搞定

 二叉树遍历

前序遍历

class Solution {
    List<Integer> list = new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
}

中序就是左中右遍历，后序就是左右中的顺序遍历，只是上面添加节点的位置不一样。

层序遍历

用队列来完成层序遍历，队列先进先出所以先放左节点进去，每一次的for循环都要把上一次中传进来的节点全部都poll出去。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null) return list;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(queue.size()>0){
            int size=queue.size();
            ArrayList<Integer> list2 = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode node= queue.poll();
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
                list2.add(node.val);
            }
            list.add(list2);
        }
        return list;
    }
}

感想：今天的题目关于二叉树比较基础，所以加了一道接雨水，这题让我想了挺久的我一直在想单调队列因为昨天学了单调队列，但是我实际用起来的时候会顾此失彼然后我看灵山的代码还没看到单调栈他前两种解法都是从竖状的角度出发的，明天来看看单调栈的解法，周赛还没来得及总结，明天得早点起了。