LeetCode-42. 接雨水【栈 数组 双指针 动态规划 单调栈】

这篇具有很好参考价值的文章主要介绍了LeetCode-42. 接雨水【栈 数组 双指针 动态规划 单调栈】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:
LeetCode-42. 接雨水【栈 数组 双指针 动态规划 单调栈】,算法题,leetcode,动态规划,算法,单调栈,双指针
输入: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

解题思路一:单调栈,维护一个单调递减栈。每当遇到当前元素大于栈顶元素就出栈,在出栈时更新答案。当遇到出栈的情况,若单调栈栈左边有一个元素则必有height[left] > height[top],有因为当前元素大于栈顶,那么可以得到当前的接到的雨水量,宽是i - left - 1,长是min(height[i], height[left]) - height[top]。根据宽度和高度即可计算得到该区域能接的雨水量。

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        stack = []
        ans = 0

        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                top = stack.pop()
                if not stack: break
                left = stack[-1]
                currWeith = i - left - 1
                currHeight = min(height[i], height[left]) - height[top]
                ans += currWeith * currHeight
            stack.append(i)

        return ans

时间复杂度:O(n) 其中 n 是数组 height的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。
空间复杂度:O(n) 空间复杂度主要取决于栈空间,栈的大小不会超过 n。

解题思路二:动态规划,其实很简单。我们只需要知道一个结论,遇到当前元素i,这个位置接的雨水量是min(leftMax[i], rightMax[i]) - height[i],即该位置左右两边最大值的小的一个减去当前位置的高度。这样就简单了,我们只需要遍历两遍数组得到左边最大值和右边最大值即可。

LeetCode-42. 接雨水【栈 数组 双指针 动态规划 单调栈】,算法题,leetcode,动态规划,算法,单调栈,双指针

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        n = len(height)
        leftMax = [height[0]] + [0] * (n - 1)
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax = [0] * (n - 1) + [height[n - 1]]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans

时间复杂度:O(n),其中 n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次,计算能接的雨水总量还需要遍历一次。

空间复杂度:O(n),其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax和 rightMax。

解题思路三:双指针,用双指针代替动态规划的两个数组,这里用leftMax , rightMax维护左右当前最大值,如果左边高度小则,left右移且更新答案;如果右边高度大于等于左边,则right左移且更新答案。

这样是一定能够保证,left += 1的时候一定是左边最大值更小。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        
        return ans

时间复杂度:O(n)
空间复杂度:O(1)文章来源地址https://www.toymoban.com/news/detail-764465.html

到了这里,关于LeetCode-42. 接雨水【栈 数组 双指针 动态规划 单调栈】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 单调栈part2 | ● 503.下一个更大元素II ● 42. 接雨水

    本篇我侧重与说一说,如何处理循环数组。 相信不少同学看到这道题,就想那我直接把两个数组拼接在一起,然后使用单调栈求下一个最大值不就行了! 确实可以! 将两个nums数组拼接在一起,使用单调栈计算出每一个元素的下一个最大值,最后再把结果集即result数组resiz

    2024年02月13日
    浏览(74)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(45)
  • map|动态规划|单调栈|LeetCode975:奇偶跳

    视频算法专题 单调栈分类、封装和总结 动态规划汇总 给定一个整数数组 A,你可以从某一起始索引出发,跳跃一定次数。在你跳跃的过程中,第 1、3、5… 次跳跃称为奇数跳跃,而第 2、4、6… 次跳跃称为偶数跳跃。 你可以按以下方式从索引 i 向后跳转到索引 j(其中 i j):

    2024年02月04日
    浏览(39)
  • leetCode-42.接雨水

    本文主要是【算法】——算法模拟的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一句:狠狠沉淀,顶峰相见 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子

    2024年01月20日
    浏览(42)
  • LeetCode42.接雨水

     这道题呢可以按列来累加,就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度,我想到了这里然后就想第i列的水其实就是第i-1列和i+1列中最小的高度减去第i列的高度,但是其实并不是,比如示例中的第5列,他的告诉是0左右两边是1,

    2024年02月11日
    浏览(37)
  • 【Leetcode】42.接雨水(困难)

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例1: 示例2: 提示: n == height.length 1 = n = 2 * 10 4 0 = height[i] = 10 5

    2024年02月16日
    浏览(41)
  • Leetcode 42. 接雨水

    题意理解 :         给定  n  个非负整数表示每个宽度为  1  的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。          左边的柱子和右边的柱子形成围栏,可以使中间能够积水         求最大的积水面积。h*w 解题思路 :         1.横向求解  

    2024年02月21日
    浏览(35)
  • 【LeetCode力扣】42. 接雨水

    目录 1、题目介绍 2、解题思路 2.1、暴力破解法 2.2、双指针法     原题链接: 42. 接雨水 - 力扣(LeetCode)   示例 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 个单位的雨水(蓝色部分表

    2024年02月08日
    浏览(36)
  • Day 42算法记录| 动态规划 08

    单词就是物品,字符串s就是背包 1.dp[0]背包啥也不要用装,true。 2. for循环,顺序很重要,所以先背包再物品 如果求组合数就是外层for循环遍历物品,内层for遍历背包 。 如果求排列数就是外层for遍历背包,内层for循环遍历物品 。 3.递归: 要么装包或者不装 添加链接描述 把

    2024年02月15日
    浏览(31)
  • Day 42 算法记录|动态规划 09 (打家劫舍)

    1.dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。 2.dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); 3.初始化,dp[0] 和 dp[1],dp[0] 一定是 nums[0],dp[1] = max(nums[0], nums[1]); 3.遍历顺序,dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历! 进一步对滚动数组

    2024年02月15日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包