当前位置: 首页 > news >正文

力扣 42. 接雨水 python AC

双指针

class Solution:def trap(self, heights):l, r = 0, len(heights) - 1maxl, maxr = 0, 0ans = 0while l < r:maxl, maxr = max(maxl, heights[l]), max(maxr, heights[r])if maxl < maxr:ans += maxl - heights[l]l += 1else:ans += maxr - heights[r]r -= 1return ans

单调栈

class Solution:def trap(self, heights):ll = []ans = 0for ind, val in enumerate(heights):while ll and val >= heights[ll[-1]]:bottom = heights[ll.pop()]if ll:h = min(heights[ll[-1]], val) - bottomans += h * (ind - ll[-1] - 1)ll.append(ind)return ans

(单调栈做法:)

--创建空列表作为栈(每轮将当前元素索引加入栈)

--遍历

  --(while)如果栈不为空且当前元素值大于等于栈中最后一位索引的值

    --弹出栈中最后一位索引并将该索引代表的值设为底的高度

    --如果栈不为空(如果为空说明左边接不了水,直接退出)

      --求出高h为(上一步弹出后)栈内最后一位索引的值和当前加入栈的值的最小值-底的高度

      --将高h*(当前加入值的索引-栈内最后一位索引-1,即两根柱子的距离)计入总和

  --(此时每轮结束)将此新元素索引加入栈

http://www.lryc.cn/news/356263.html

相关文章:

  • The 2022 ICPC Asia Nanjing Regional Contest - External D
  • 2024年蓝桥杯B组C++——复盘
  • 微调Llama3实现在线搜索引擎和RAG检索增强生成功能
  • 【软件工程】【23.04】p1
  • Flutter 中的 ColoredBox 小部件:全面指南
  • 【LeetCode 随笔】面试经典 150 题【中等+困难】持续更新中。。。
  • SwiftUI中AppStorage的介绍使用
  • iCloud 照片到 Android 指南:帮助您快速将照片从 iCloud 传输到安卓手机
  • 知识点总结
  • Python并发与异步编程
  • 动态内存管理—C语言通讯录
  • 美光EMMC芯片丝印型号查询 8LK17/D9PSK, OXA17/JY997
  • win32-鼠标消息、键盘消息、计时器消息、菜单资源
  • springboot项目部署到linux服务器
  • MagicLens:新一代图像搜索技术和产品形态
  • [9] CUDA性能测量与错误处理
  • Java学习四
  • Vue 父组件使用refs来直接访问和修改子组件的属性或调用子组件的方法
  • 范罗士、希喂、安德迈爆款宠物空气净化器哪款好?深度对比测评
  • SAP OBYC自动记账 详解
  • 《NoSQL数据库技术与应用》 MongoDB副本集
  • Flutter 中的 DropdownButtonFormField 小部件:全面指南
  • 哈希算法教程(个人总结版)
  • Nocobase快速上手 -第一个collection
  • 吴恩达2022机器学习专项课程C2W2:2.19 sigmoid函数的替代方案 2.20如何选择激活函数 2.21 激活函数的重要性
  • 循序渐进Docker Compose
  • 怎样查看JavaScript中没有输出结果的数组值?
  • 强化学习学习笔记-李宏毅
  • 吴恩达深度学习笔记:超 参 数 调 试 、 Batch 正 则 化 和 程 序 框 架(Hyperparameter tuning)3.8-3.9
  • SQL 语言:数据控制