南昌市住房城乡建设委门户网站/游戏推广是什么工作

原文链接
原文是带着图片讲解，过程还算详细

上题是一个对题目的举例说明
本次解题中用这个图

我认为这个图涵盖了可能出现的情况，讲解会比较好一点
第一种方法是暴力法，时间复杂度为O （n^2） 空间复杂度为O（1）

public int trap02(int[] height) { int sum = 0;   //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2    for (int i = 1; i < height.length - 1; i++) { int max_left = 0;       //找出左边最高        for (int j = i - 1; j >= 0; j--) {  if (height[j] > max_left) {  max_left = height[j];  }       }        int max_right = 0;       //找出右边最高       for (int j = i + 1; j < height.length; j++) { if (height[j] > max_right) {  max_right = height[j];   }       }       //找出两端较小的       int min = Math.min(max_left, max_right); //只有较小的一段大于当前列的高度才会有水，其他情况不会有水  if (min > height[i]) { sum = sum + (min - height[i]);       }   }   return sum;
}

每一步的前进都让 当前元素的前边和后边比较，找出前边后边的最小值然后再和当前元素比较，看是否能放入水，代码不好直接阅读的话可用箭头在上图中来一步一步前进
，画图有助于理解

第二种方法为双指针法
具体分析可以点文章开头的原文阅读，此处稍微提及

大体的思想就是从左右两边开始遍历 如果左边的最高的小于右边的最高的，那么就从左边开始前进，找能存放的水量，反之也一样，在指针前进的过程中更新最大值，通过两边的最大值比较到底应该从哪边走，因为存水量取决于最小的那一端

public int trap(int[] height) {if (height.length == 0) return 0;int left = 0;int right = height.length-1;int leftMax = 0;int rightMax = 0;int result = 0;while (left <= right) {if (leftMax < rightMax) {result += leftMax - height[left] > 0 ?leftMax - height[left] : 0;leftMax = Math.max(leftMax, height[left]);left++;} else {result += rightMax - height[right] > 0 ?rightMax - height[right] : 0;rightMax = Math.max(rightMax, height[right]);right--;}}return result;}

时间复杂度为O（n^2）空间复杂度为O（1）
第三种方法是按照行求
具体看原文
https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/