Alangy's Blog
这个人很懒，什么都没有写
Toggle navigation
Alangy's Blog
首页
LeetCode刷题记录
开发
关于我
文章归档
标签
接雨水
2023-02-17 19:52:17
50
0
0
admin
难度：leetcode hard 给定 n 个非负整数表示每个宽度为 1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 原文地址： https://leetcode.cn/problems/trapping-rain-water/  这道题的算法原理较好想到，其实就是确定任何一点的左右最大值，就可以得知这个点能够装到的最高的水。难在如果先做一遍遍历再将最大值存在数组中，无法做到从O(N)空间到O(1)的优化。 实际使用的方法是难点【双指针】。其实就是，维护left指针和right指针，如果当前left点的高度比right更低，那么left点的储水量就已知了（因为right向左移动，新值一定比right更大，因此，**限制**当前left点储水高度的，一定是left点的高度。）在求出left点的储水量后，向右边移动left即可。如此继续这个步骤，直到left==right。 这道题其实和leetcode medium中的盛水最多的容器很相似，从两端开始贪心，在找到当前限制条件（短板）后，提高短板到下一个极值点。
上一篇:
a>b Problem
下一篇:
找出字符串中第一个匹配项的下标
0
likes
50
Weibo
Wechat
Tencent Weibo
QQ Zone
RenRen
Submit
Sign in
to leave a comment.
No Leanote account?
Sign up now.
0
comments
More...
Table of content
admin
No Leanote account? Sign up now.