leetcode
leetcode 1 ~ 50
接雨水

接雨水

难度:

标签:

题目描述

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

代码结果

运行时间: 32 ms, 内存: 15 MB

// Java solution using streams to calculate trapped rainwater
// Similar idea but with streams to calculate left and right maximum arrays
import java.util.stream.IntStream;
 
public class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n <= 1) return 0;
 
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
 
        // Fill leftMax array using streams
        IntStream.range(1, n).forEach(i -> leftMax[i] = Math.max(leftMax[i - 1], height[i]));
 
        // Fill rightMax array using streams
        rightMax[n - 1] = height[n - 1];
        IntStream.iterate(n - 2, i -> i >= 0, i -> i - 1).forEach(i -> rightMax[i] = Math.max(rightMax[i + 1], height[i]));
 
        // Calculate the trapped water using streams
        return IntStream.range(0, n).map(i -> Math.min(leftMax[i], rightMax[i]) - height[i]).sum();
    }
}

解释

方法:

这个题解使用了单调栈的思路。维护一个单调递减的栈，栈中存储柱子的索引。当遇到一个高度大于栈顶索引对应高度的柱子时，说明形成了一个凹槽，可以接雨水。通过计算凹槽的宽度和高度，可以得到该凹槽能接的雨水量。将这些雨水量累加起来就是最终答案。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
你是如何确定使用单调栈而不是其他数据结构（如数组或队列）来解决这个问题的？
▷
单调栈的选择是基于其能有效处理问题中涉及的序列局部最大或最小值的特性。在接雨水问题中，我们需要找到每个柱子左右两边比它高的柱子，以确定这个柱子可以接的雨水量。单调栈可以在遍历数组的同时，通过维护一个递减的栈来快速找到左边和右边第一个比当前柱子高的柱子，从而计算雨水量。这种方法相较于数组和队列，可以更直接地解决问题并且减少不必要的重复计算，提高算法效率。
🦆
在单调栈中，当当前柱子的高度大于栈顶柱子高度时，你是如何计算凹槽的宽度的？
▷
在单调栈中，当遇到一个当前柱子的高度大于栈顶柱子的高度时，栈顶的柱子索引表示凹槽的底部。此时，栈顶下一个元素的索引就是凹槽左边界的柱子，当前索引是凹槽右边界的柱子。凹槽的宽度可以通过右边界的索引减去左边界索引再减一来计算，即 `i - stack[-1] - 1`，这里的 `i` 是当前柱子的索引，`stack[-1]` 是凹槽左边的柱子索引。
🦆
在处理等高的柱子时，为什么要将栈中等高的柱子全部弹出？这样做有什么特别的意义或优势？
▷
在处理等高的柱子时，将栈中等高的柱子全部弹出是为了避免重复计算雨水的存储量。如果栈中有多个等高的柱子，这些柱子之间不可能存储任何雨水，因为它们的高度相同，水会从两者之间流走。只有最左边的等高柱子可能与更左边的一个更高的柱子形成凹槽来存储雨水。因此，保留最左侧的等高柱子，删除其他等高柱子可以简化问题的处理，减少不必要的计算。
🦆
如果栈顶的柱子高度等于当前柱子的高度，这种情况下的处理逻辑是怎样的？在你的代码中没有特别提及。
▷
在本题解的逻辑中，如果栈顶柱子的高度等于当前柱子的高度，这种情况实际上并没有进行特别的处理。这是因为等高的栈顶柱子和当前柱子之间无法形成有效的凹槽来存储雨水，因此可以视为不影响总雨水量的计算。在实际实现中，遇到此种情况通常意味着当前柱子不会对栈产生影响，或者可以将栈顶的柱子替换为当前柱子的索引，以便后续可能的更高柱子能正确计算宽度。

相关问题

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

 

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

 

提示：

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

 

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

 

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

 

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

接雨水 II

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

 

示例 1:

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

 

提示:

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200
  • 0 <= heightMap[i][j] <= 2 * 104

 

倒水

倒水
缺失的第一个正数字符串相乘