LeetCode42题动态规划 - 接雨水

爱被打了一巴掌 2023-01-13 01:48 124阅读 0赞

### 文章目录 ###

*  理论
 *  题目描述
 *  思路分析
 *   *  确定转换方程
     *  确定初始值
     *  从小到大依次计算
 *  AC代码
 *  总结

> 程序员如果仅满足curd的话，那么35岁危机很快就会到来。在大学期间学校主打的应该也都是算法思维。今天我们已大学里学的一个理论为基础展开讨论—动态规划

# 理论 #

*  将一个大问题细化为子问题。即转换经过一层一层的细化最终转为话小问题或者说转换为已知解。
 *  话不多说，我们直接已leetcode42–接雨水问题展开

# 题目描述 #

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

![21d9b78465c3806c2a0731a770f160cc.png][]

示例 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
    0 <= n <= 3 * 104
    0 <= height[i] <= 105

# 思路分析 #

![9bb5fc856684f4324b9c445497ed5c07.png][]

*  上面是笔者的提交记录，在速度上还是蛮快且没有占用太多内存。速度上目前是leetcode中java程序超越100%；内存使用上最好的一次是超越98%；下面我们先来分析一下解题思路
 *  学习过动态规划的都知道正常的动态规划有几步骤。

## 确定转换方程 ##

*  因为动态规划就是将大问题分解成小问题。如果我想要获取100块钱。假设面值只有1元，那么我想活得100元就必须先获得99元。从100到99的过程就是我们分解的过程。依次类推我们最终只需要获取到1元就可以推倒出100元了。这个过程和递归还是有区别的。今天我们不做赘述。
 *  在接雨水题目中我们当前接水量是受后面柱子的影响的。
 *  为了后续方便演示我们约定如下称谓

<table> 
 <thead> 
  <tr> 
   <th>简称</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Zn</td> 
   <td>第几根柱子；即图中的坐标</td> 
  </tr> 
  <tr> 
   <td>Sn</td> 
   <td>表示截止到第n根柱子，整体形成的水池容量</td> 
  </tr> 
  <tr> 
   <td>SDn</td> 
   <td>表示当前第n根柱子垂直方向的水量</td> 
  </tr> 
  <tr> 
   <td>Zmax</td> 
   <td>表示截止到目前出现的最高的柱子的高度</td> 
  </tr> 
  <tr> 
   <td>Sm,n</td> 
   <td>表示第m到第n块柱子形成的水池</td> 
  </tr> 
 </tbody> 
</table>

![913ec36e46da9b3d3d9ef6f6242d84c0.png][]

*  就像题目中一样在走到第六块时，此时Z6=0 .表示第六块的柱子所形成的水池是0 。 但是当第七块是会与第六块和第五块形成水池。
 *  所以假设Fx表示从1开始到第x块柱子形成的水池容量。

![3e3d841824f74eddd1b7dbc1e9b6cbaf.png][]

## 确定初始值 ##

*  这道题的初始值考虑不是很多。第一块很明显是0 ，即S0=0

## 从小到大依次计算 ##

![2b793bd451dc4ea4c6842da41b7202da.png][]

*  第一步平地高楼。S0=0

![705027467018a93ec4cd4979b980cc2c.png][]

*  第一步，我们直接从第二根柱子开始，此时没有最高柱子是不会形成水池的。我们计算结果S2=0;

![377de2d846ba4cf51540f4f1b0aa6d1d.png][]

*  然后我们将指针移动到第三根柱子，Z3=0我们理解为平地，平地是不会形成水池的。所以S3=S2=0;

![00bd83b140532409ad11d1b516e655a2.png][]

*  next，我们走到了第四根柱子，Z4=2,当前最高的柱子是Z2=1;注意这里Z4还没有加入最高柱子竞争中。所以Zmax=Z2=1。按照我们的推导公式。在\[Z2~Z4)中不存在不低于Z4的柱子,所以`S4=S2+S4,2`
 *  `S4,2`表示第二块到第四块形成的水池容量`S4,2=(4-2-1)*min(Z2,Z4)-柱子容量=1`
 *  所以S4=0+1=1;

![280273088b48bb96f4394afc3742bb2b.png][]

*  现在指针走到了第五根柱子，第五根和第四根之间没有空隙，所以S5=S4=1;

![b251830359e189d2e8dce19388e3b57c.png][]

*  在第三根柱子的时候我们得出理论，平地是不可能有水池形成的。所以这里第六根柱子直接忽略。。
 *  S6=S5=1

![938d3ec944a9efe619a49764bb63fa00.png][]

*  当前最高的柱子是Z4。在Z4~Z7中存在Z5是不低于Z7的。所以S7=S5+S7,5
 *  `S7,5`表示第五根到第七根的水池=1
 *  S7=1+1=2.

![94c5d4c725ff13f260b147966d096047.png][]

*  Z8=3。在Zmax~Z8中没有不低于Z8的。所以直接与Zmax形成水池。
 *  `S8=S4+S8,4`
 *  `S8,4=(8-4-1)*min(Zmax,Z8)-sum(Zmax+1,Z7)=3*2-(1+1)=6-2=4`
 *  `S8=1+4=5`

![ec52c0004769cc3c7a723e8823bb6ea0.png][]

*  第八跟和第九根没有缝隙，所以没有水池。
 *  `S9=S8=5`

![d26b572671acf207007090661f3701bb.png][]

*  S10和S9没有缝隙，所以也没有水池
 *  `S10=S9=6`

![6be2214827ca870f899ca96e896f8662.png][]

*  在第11根柱子时，我们Zmax=Z8.我们找到了Z9不低于Z11。所以`S11=S8+S11,9=5+1=6`
 *  所以最终答案就是6 。
 *  到这里我将整个过程已动画的形式展现出来。应该可以理解到动态规划的意思了吧。
 *  下面我们直接看看代码实现吧。

# AC代码 #

*  为了方便读者演示效果。下面的程序是完整的代码。只需要复制过去导入包后直接运行即可。

public int trap(int[] height) { 
        if (height.length == 0) { 
            return 0;
        }
        int[] result = new int[height.length];
        int heighMaxIndex = 0;
        for (int i = 1; i < height.length; i++) { 
            if (height[i] == 0) { 
                result[i] = result[i - 1];
                continue;
            }
            int secondMaxIndex = i-1;
            boolean flag = false;
            for (int j = i - 1; j >= heighMaxIndex; j--) { 
                if (height[j] >= height[i]) { 
                    //截至柱
                    int x =i-j-1;
                    int y = getHeightCrossX(height,j,i);
                    result[i] = result[j] + x * height[i] - y;
                    flag=true;
                    break;
                }
                if (height[j] > height[secondMaxIndex]) { 
                    secondMaxIndex = j;
                }
            }
            if (flag) { 
                continue;
            }
            int y = getHeightCrossX(height, secondMaxIndex, i);
            result[i]=result[secondMaxIndex]+height[secondMaxIndex]*(i-secondMaxIndex-1)-y;
            if (height[heighMaxIndex] < height[i]) { 
                heighMaxIndex=i;
            }
        }
        return result[result.length-1];
    }
    
    private int getHeightCrossX(int[] height,int j, int i) { 
        int y = 0;
        for (int k = j + 1; k < i; k++) { 
            y += height[k];
        }
        return y;
    }
    
    public static void main(String[] args) { 
    
        LeetCode42 leetCode = new LeetCode42();
        System.out.println(leetCode.trap(new int[]{ 0,1,0,2,1,0,1,3,2,1,2,1}));
    
    }

# 总结 #

*  接雨水问题是典型的动态规划问题，只不过他的前一步会受到后面几步的影响。所以我们的推导公式需要找到不受影响的上一步。也就是我们推到中称的最高柱。因为最高柱的形成相当于是一堵墙，墙的左边是受保护的。

![c684f1d845e2a37d5def66a748b6527f.png][]

[21d9b78465c3806c2a0731a770f160cc.png]: /images/20221022/4dbd45d56eb94c74bc52a932f4bee2b8.png
[9bb5fc856684f4324b9c445497ed5c07.png]: /images/20221022/fb516c4a0efc4fed9061c4d70f45f547.png
[913ec36e46da9b3d3d9ef6f6242d84c0.png]: /images/20221022/594a9ba57e984e77ab0a8d09f8fab78a.png
[3e3d841824f74eddd1b7dbc1e9b6cbaf.png]: /images/20221022/b70ef7bd8b6c43559c9f21f0d9c85557.png
[2b793bd451dc4ea4c6842da41b7202da.png]: /images/20221022/8c43e0068eaa4b728944825099156c48.png
[705027467018a93ec4cd4979b980cc2c.png]: /images/20221022/9b0ef6c800ff4c16b90ec4b20b19fdda.png
[377de2d846ba4cf51540f4f1b0aa6d1d.png]: /images/20221022/a07987b05a904ad88947dc6e4a5d491a.png
[00bd83b140532409ad11d1b516e655a2.png]: /images/20221022/445a6fa2586541b7a36915251dd0372b.png
[280273088b48bb96f4394afc3742bb2b.png]: /images/20221022/fcb325f13dbf468a862affb170440311.png
[b251830359e189d2e8dce19388e3b57c.png]: /images/20221022/0a3c2e8028324920b61b402befef4c47.png
[938d3ec944a9efe619a49764bb63fa00.png]: /images/20221022/da6cd5c19e0b431faea211808b4c2d4f.png
[94c5d4c725ff13f260b147966d096047.png]: /images/20221022/2572770996ed4b108d3a874520e88d39.png
[ec52c0004769cc3c7a723e8823bb6ea0.png]: /images/20221022/d77536fa93bc4e128ffa1ae73d0b1745.png
[d26b572671acf207007090661f3701bb.png]: /images/20221022/d5f5997521114683b6db3605771408c5.png
[6be2214827ca870f899ca96e896f8662.png]: /images/20221022/dc27ab2bafa7425da5d8af62bd61a8fc.png
[c684f1d845e2a37d5def66a748b6527f.png]: /images/20221022/680c76b3e03c4b11b61c6b6f3578c8d7.png