力扣接雨水

2024-09-08 05:12
文章标签 力扣 雨水

本文主要是介绍力扣接雨水,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定 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

 动态规划:

class Solution {public int trap(int[] height) {int len = height.length;// 如果数组长度为0,返回0if(len == 0){return 0;}// 创建一个数组用于存储每个位置左侧的最大高度int[] leftMax = new int[len];for(int i = 1; i < len; i++){// 更新当前点的左侧最大高度leftMax[i] = Math.max(height[i-1], height[i]);}// 创建一个数组用于存储每个位置右侧的最大高度int[] rightMax = new int[len];for(int i = len-2; i >= 0; i--){// 更新当前点的右侧最大高度rightMax[i] = Math.max(height[i], height[i+1]);}int ans = 0;// 计算每个位置能够存储的水量for(int i = 0; i < len; i++){ans += Math.min(leftMax[i], rightMax[i]) - height[i];}// 返回能够存储的总水量return ans;}
}

单调栈解决

import java.util.Stack;class Solution {public int trap(int[] height) {// 初始化总雨水量为0int totalWater = 0;// 创建一个栈用于存储数组索引Stack<Integer> stack = new Stack<>();// 遍历每个高度for (int i = 0; i < height.length; i++) {// 当栈非空且当前高度大于栈顶所指的高度时while (!stack.isEmpty() && height[i] > height[stack.peek()]) {// 取出栈顶的高度索引int top = stack.pop();// 如果栈为空,跳出循环if (stack.isEmpty()) {break;}// 计算当前柱子的宽度int distance = i - stack.peek() - 1;// 计算能形成的水位高度差int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];// 计算当前能积的水量并加到总水量中totalWater += distance * boundedHeight;}// 将当前索引入栈stack.push(i);}// 返回总雨水量return totalWater;}
}

工作原理

  1. 单调递减栈:栈中存储的是高度数组的索引。栈内元素对应的高度从栈底到栈顶是非递增的。
  2. 遍历高度数组:对于每一个高度,若其大于栈顶元素所指的高度(即找到一个可能的凹槽),则计算当前凹槽的水量。
  3. 水量计算
    • 宽度:凹槽宽度为当前索引 i 与栈顶下一个元素的索引之差再减去 1。
    • 高度:水位高度差为 min(当前高度, 栈顶下一个高度) - 栈顶高度
  4. 累加水量:将计算出的水量累加到总水量中。

在计算接雨水的过程中,水的高度取决于柱子之间的最低高度。具体来说,水只能被较矮的柱子挡住。因此,关键在于找到最低的柱子,并根据它来计算可能存储的水量。

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

判断逻辑

  1. 水量计算基础

    • 对于 height[left] < height[right] 的情况,由于 leftMax 是从左侧移动过程中遇到的最大高度,而 rightMax 是从右侧移动过程中遇到的最大高度,因此:
      • 当前柱子 height[left] 左侧的最大高度 leftMax 是可靠的。
      • 但是,右侧的最大高度 rightMax 还可能会更新。因此,此时计算 left 位置的积水量是安全的。
  2. 为什么选择较小的高度

    • 如果 height[left] < height[right],意味着在当前位置 left,其右侧有更高的柱子。这个较高的柱子可以帮助挡住雨水。因此可以确定 leftMax 是最小的限制条件,用它来计算当前位置可能存储的水量是安全的。
    • 如果 height[left] >= height[right],那么右侧柱子在此时成为决定因素,左侧的 leftMax 没有影响,应该通过 rightMax 计算右侧的水量。

例子说明

假设 height[left] = 2height[right] = 5

  • left 侧低于 right:可以确定在左侧 left 柱子能容纳的水量只取决于 leftMax。因此,将 left 向右移动并计算 leftMax - height[left]

  • 如果反过来:如果左侧高于或等于右侧,则右侧可能会积水,因此移动 right 向左并计算 rightMax - height[right]

总结

这一判断的核心在于:

  • 小于:左侧可能有积水,计算左侧。
  • 大于等于:右侧可能有积水,计算右侧。

初始状态下的 right 指针

  • right 指针初始位置:它从数组的最右端开始。
  • left 指针初始位置:它从数组的最左端开始。

初始比较:height[left] < height[right]

在算法的开始阶段,我们用 height[left] < height[right] 来判断接下来的行动。虽然 right 一开始位于数组的最右边,但这并不影响算法的正确性,原因如下:

  1. rightMax 的初始化

    • 初始时,rightMax 会等于 height[right]。因为 right 指针在最右端,所以 rightMax 一开始就是数组最右边的那个高度。
    • 随着 right 指针向左移动,rightMax 会逐渐更新为更大的值,直到遍历完所有右边的柱子。
  2. 初始状态的判断

    • 在开始时,算法将 leftright 的柱子高度进行比较。
    • 如果 height[left] < height[right],说明左边的柱子比右边矮。在这种情况下,右边更高的柱子可以“挡住”水,因此左边柱子上方可能会有积水,这时候左边的积水高度是可以确定的,所以移动 left 指针并计算水量。
    • 如果 height[left] >= height[right],算法会移动 right 指针。此时,不会计算 left 指针位置的积水,而是继续查看右边的柱子是否可能形成积水。
  3. 意义在于确定安全的水量

    • 通过比较 height[left]height[right],算法确保了在当前位置计算水量时,有足够的信息保证水量是准确的。
    • rightMaxleftMax 在算法执行过程中不断更新,确保算法总是在安全的条件下进行计算。

实际意义

即使 right 指针最开始位于最右边,这个初始比较也有意义,因为它为整个算法奠定了基础。我们可以通过这个初始比较,确保在移动 leftright 指针时,计算的积水量是正确且安全的。

举个例子

假设 height 数组为 [1, 0, 2, 1, 0, 1, 3]leftright 初始分别在位置 06

  • left 开始为 1right 开始为 3
  • 第一次比较时,height[left] = 1height[right] = 3,显然 1 < 3,我们可以放心地移动 left 指针,因为左边的积水高度确定不会超过 leftMax

总之,这一步比较对于算法的正确性和水量计算至关重要,即使 right 指针最初处于最右边,也依然有效且必要。

这篇关于力扣接雨水的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147209

相关文章

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (

Java中等题-整数替换(力扣)

给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2替换 n 。如果 n 是奇数,则可以用 n + 1或n - 1替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 输入:n = 8输出:3解释:8 -> 4 -> 2 -> 1 示例 2: 输入:n = 7输出:4解释:7 -> 8 -> 4 -> 2 -> 1或 7 ->

力扣 | 递归 | 区间上的动态规划 | 486. 预测赢家

文章目录 一、递归二、区间动态规划 LeetCode:486. 预测赢家 一、递归 注意到本题数据范围为 1 < = n < = 20 1<=n<=20 1<=n<=20,因此可以使用递归枚举选择方式,时间复杂度为 2 20 = 1024 ∗ 1024 = 1048576 = 1.05 × 1 0 6 2^{20} = 1024*1024=1048576=1.05 × 10^

每日一题,力扣leetcode Hot100之198.打家劫舍

这一道题乍一看可以双层循环暴力解,但是仔细一想有可能最大利益并不是一家隔着一家偷,我可以间隔很多家偷,所以 这个题的思路还是有点像爬楼梯,用动态规划解。 首先确立动态规划的初始条件: 1.dp[0]=nums[0]只有一家 2.dp[1]=max(nums[0],nums[1])有两家选一家多的 然后确立动态规划的循环条件: dp[i]应该是什么 1.第i家能拿,那么dp[i]=n

求二叉树的深度——(力扣c语言)

题目如下: 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1: 输入:root = [3,9,20,null,null,15,7]输出:3 示例 2: 输入:root = [1,null,2]输出:2 题目解析: 上题就是要利用递归对目标进行访问找到叶子节点之后记录并返回到根节点之后对左右两个