数据结构|回顾下接雨水问题算法|java|接雨水|双指针|动态规

前两天看了下算法题目，瞅到了接雨水问题，看了下自己之前写的解题思路，使用的方法居然是栈！我瞬间惊呆了。
在我印象中，栈这个结构，除了队列或者其他很明显的业务要求，我才会使用，真心是-----不熟！
可能是抱着学习的态度，当时专门使用stack这个结构进行解题。不过仔细看了下，还是有点绕，复杂度倒是不高，不过理解起来有点吃力，估计看完之后，会和金鱼一样-----保留七天的记忆，后面能不能记起来，完全凭天意了！

文章图片

不过就这个问题，动态规划他不香么？双指针他不简单么？写个代码来看下。

/** * desc:接雨水问题 * * @author 笔下天地宽 * @date 2022/3/29 13:57 */ public class Trip {public static void main(String[] args) { Integer[] height = {0,1,0,2,1,0,1,3,2,1,2,1}; Integer result = solutionForPlan(height); //Integer result = solutionForPoint(height); System.out.println("result：" + result); }/** * desc: 动态规划 * * @param arr * @return */ public static Integer solutionForPlan(Integer[] arr) {Integer[] leftArr = new Integer[arr.length]; Integer[] rightArr = new Integer[arr.length]; leftArr[0] = arr[0]; rightArr[arr.length -1] = arr[arr.length-1]; int total = 0; // 从左往右左侧的最高值 for (int i = 1; i < arr.length; i++) { if(arr[i] > leftArr[i-1]){ leftArr[i] = arr[i]; } else { leftArr[i] = leftArr[i-1]; } } // 从右往左，右侧的最高值 for (int i = arr.length-2; i >0 ; i--) { if (arr[i] >rightArr[i+1]){ rightArr[i] = arr[i]; } else { rightArr[i] = rightArr[i+1]; } }// 当前水柱小于左侧最高值与右侧最高值，能存水，去左右较低的减去当前 for (int i = 0; i < arr.length; i++) { if (leftArr[i]>arr[i] && rightArr[i] > arr[i]){ total += (leftArr[i]-arr[i]) < (rightArr[i]-arr[i]) ? (leftArr[i]-arr[i]):(rightArr[i]-arr[i]); } } return total; }public static Integer solutionForPoint(Integer arr[]){ //左右指针 int left = 0; int right = arr.length -1 ; int result = 0; // 指针没有交互 while (left < right ){ if (arr[left] < arr[right]){ // 指针右移，左侧小于右侧，无法积水，继续右移 if (arr[left] < arr[left+1]) { left += 1; } else { // 右侧凹陷，能积水。因为左侧指针小于右侧指针，故右侧最高点高些，积水以低矮为准，直接减 int temp = arr[left]; while (arr[++left] <= temp){ result += temp - arr[left]; } } } else { // 同理，指针左移 if (arr[right] < arr[right-1] ){ right -= 1; } else { // 左侧凹陷，计算积水 // 注：左右指针无论如何移动，都是向最高的柱子移动，每次移动碰到和自己一样高的，都要返回判断while(left < right)决定是否跳出循环 int temp = arr[right]; while (arr[--right] < temp){ result += temp - arr[right]; } } } } return result; } }

说下一下主要思路，(#^.^#)

文章图片

动态规划主要思路：某一个可以接水的地方，左右必然都有比当前这个点高的柱子。当前节点往左，最高的柱子a，和从当前节点往右，最高的柱子b，a与b的较小值，减去当前的柱子的高度（接多少雨水由矮一点的柱子决定），就是当前能接的雨水。
首先，记录从左到右每个节点左侧的最高柱子，放到数组left中，然后记录从右往左记录每个节点右侧的最高柱子，放到right中。
接着，遍历原始数组对，每个柱子i都有了left[i] 和right[i] 这两个最侧最高和右侧最高，做个判断和相减，就计算出水柱，然后，累加就行。
双指针思路：假设最左节点与最右节点有一个指针，两个指针都往中间移动，指针碰到的时候，也就是说到了同一根柱子上（left 同时，接水的时候，初始高度肯定不能小于接完水的高度，不然你过了最高点，指针过头了就麻烦了。
看下左侧指针，首先，当前柱子比右侧柱子低，那就往右移动。碰到比自己高的，肯定没法接水啊，返回while继续判断（防止移动过头），碰到比自己低的（比如i），那就相减，就能计算出i的水柱，因为左指针柱子比右指针柱子低，i又比左指针柱子低，自然能积水（左指针柱子 - i的高度）。然后继续右移，一旦遇到不比自己矮的柱子，也就是不能积水了，就返回重新判断，看看需要哪个指针移动。
右指针，类似，从右往左移动，也是判断+计算积水，各位老铁应该都懂，