力扣算法学习day41-2
42-接雨水
题目
代码实现
class Solution {
// public int trap(int[] height) {
// // 直接想到的方法 几何解法：速度 0ms，哈哈哈，第一次直接做出来hard题目。
// // 思路：求图形中雨水中的数量比较难求，但是可以将整个看成一个长方形，然后去减去小长方形的面积和每个柱子。
// // 这里条件1 <= n <= 2 * 10的4次方，0 <= height[i] <= 10的5次方，所以乘积为2* 10 的 9次方。
// // 没有超过int类型的上限，所以该方法应该可以。
// // 方法详解：
// // 从左到到右遍历到最大值的地方，从右到左也遍历到最大值的地方，长方形的面积取最大值 * 数组长度，然后从左
// // 到右遍历，每次 长方形的面积需要 - 最大高度 + 目前最高高度，每次遇到新的目前最高高度需要及时更新，如果
// // 遇到最高高度，直接结束循环，在同理从右到左再遍历一次。最后还需要遍历一次，减去柱子的面积，最后面积就是
// // 题目需要求的雨水的数量。
// int maxHeight = height[0];
// // 求当前数组的最大高度
// for(int i = 1;i < height.length;i++){
// if(maxHeight < height[i]){
// maxHeight = height[i];
// }
// }
// int area = maxHeight * height.length;
// // 第一次遍历，从左到右，每次 长方形的面积需要 - 最大高度 + 目前最高高度
// int tempHeight = 0;
// for(int i = 0;i < height.length;i++){
// // 如果当前高度是最高高度，直接退出
// if(height[i] == maxHeight){
// break;
// }
// if(height[i] > tempHeight){
// tempHeight = height[i];
// }
// // 减去面积
// area = area - maxHeight + tempHeight;
// }
// // 第二次遍历
// tempHeight = 0;
// for(int i = height.length - 1;i >= 0;i--){
// if(height[i] == maxHeight){
// break;
// }
// if(height[i] > tempHeight){
// tempHeight = height[i];
// }
// area = area - maxHeight + tempHeight;
// }
// // 最后需要遍历一次减去柱子占的面积
// for(int i = 0;i < height.length;i++){
// area -= height[i];
// }
// return area;
// }
// public int trap(int[] height) {
// // 双指针法 速度：500+ms(测试两次507/535)
// // 思路: 遍历每一列(除开头和尾，因为头和尾不能上面会装雨水),求这一列的左边的最高lHeight，和右边
// // 的最高柱子rHeight，然后这一列上面能够存储的雨水就是 Math.min(lHeight,rHeight) - height[i]
// // 结果如果大于0，说明上面可以接收一定量的雨水，遍历的同时统计雨水总量即可。
// int result = 0;
// // 遍历每一列
// for(int i = 1;i < height.length - 1;i++){
// int lHeight = height[i];
// int rHeight = height[i];
// // 找左边最高
// for(int j = i - 1;j >= 0;j--){
// if(height[j] > lHeight){
// lHeight = height[j];
// }
// }
// // 找右边最高
// for(int j = i + 1;j < height.length;j++){
// if(height[j] > rHeight){
// rHeight = height[j];
// }
// }
// // 计算雨水
// int temp = Math.min(lHeight,rHeight) - height[i];
// if(temp > 0){
// result += temp;
// }
// }
// return result;
// }
// public int trap(int[] height) {
// // 动态规划：速度：1ms
// // 思路：双指针很明显是有重复计算的，很容易想到的是用动态规划来优化其求左右最大值的过程，那么造一个
// // dpL 代表当前位置i左边最大值，造一个dpR 代表当前位置i右边的最大值。那么其他逻辑一样即可。
// // 迭代公式:(比较简单，就不解释了)
// // dpL[i] = Math.max(dpL[i-1],height[i]);
// // dpR[i] = Math.max(dpR[i+1],height[i]);
// int[] dpL = new int[height.length];
// int[] dpR = new int[height.length];
// int result = 0;
// // 初始化
// dpL[0] = height[0];
// dpR[height.length - 1] = height[height.length - 1];
// // 先求两个dp数组的值。
// for(int i = 1;i < height.length;i++){
// dpL[i] = Math.max(dpL[i-1],height[i]);
// }
// for(int i = height.length - 2;i >= 0;i--){
// dpR[i] = Math.max(dpR[i+1],height[i]);
// }
// // 然后和双指针求雨水的逻辑是一样的。
// for(int i = 1;i < height.length - 1;i++){
// int temp = Math.min(dpR[i],dpL[i]) - height[i];
// if(temp > 0){
// result += temp;
// }
// }
// return result;
// }
public int trap(int[] height) {
// 单调栈(单调增 从栈顶到栈底 依次递增) 速度：2ms
// 思路：相当于求一个凹槽(准确的说是一个凹层)的雨水面积，这个方法要接合图形看比较好理解，就是从左到右遍历，
// 在这之前先创建一个stack用作单调栈(注：stack存储height坐标)，先将第一个height元素放入，之后的遍历规则是：
// 1.遇到的元素(height数组对应高度)如果小于栈顶元素，就压入栈，因为形成凹层 会先由小的形成。
// 2.遇到的元素(height数组对应高度)如果等于栈顶元素，那就弹出栈顶，然后加入新元素的height坐标，这里之所以
// 加入新元素是因为如果这个数是凹槽底，那么它不参与计算，只用其柱子高度用于计算。如果它是凹槽左边的支柱，
// 那么如果它有重复的，只能取最右边的那个。这里画个图理解好些。
// 3.如果遇到大于栈顶，那么需要弹出栈顶，用引用mid接收，height[mid]代表它的高度，这是，弹出后栈顶肯定大于
// height[mid]，这时则需要计算，这里需要注意的是不会有小于的情况，这是前面两个规则决定的了。当然，也有可能
// 出现为空的情况，如果为空，说明是没得嘛，那个形状就是单调增嘛，所以直接把这个遇到(遍历)的元素放入就行了。
// 具体的计算是：
// 宽 = 遍历到的这个元素坐标 - 栈顶元素坐标 - 1 高 = Math.min(栈顶元素对应高度,当前元素高度) - height[mid]
// 面积(雨水的数量) = 宽 * 高
LinkedList<Integer> stack = new LinkedList<>();
int result = 0;
stack.push(0);
for(int i = 0;i < height.length;i++){
while(!stack.isEmpty() && height[i] >= height[stack.peek()]){
// 相等的情况
if(height[i] == height[stack.peek()]){
stack.pop();
break;
}
int mid = stack.pop();
// 不是凹槽
if(stack.isEmpty()){
break;
}
int x = i - stack.peek() - 1;// 求宽
int y = Math.min(height[i],height[stack.peek()]) - height[mid];
int area = x * y;
result += area;
}
stack.push(i);
}
return result;
}
}