OJ刷题总结 2
OJ刷题总结 2
上次更新还是上周。。不是摆烂了,是这周实在是太忙碌了。。。最近科研不是很顺畅,复现个3dgs,环境配不好。。很奇怪。。。稍微看了点代码理解了一下。。。工作到晚上9点。。剩下时间,在图书馆学习下算法,写个总结。
Leetcode 11
盛最多水的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
借鉴一下leetcode的例图:
假设说,我们有两个指针,一左一右。分别指向红色的两个柱子。
这个时候,我们选中红色柱子中的一个柱子,和矮的的柱子构成容器(也就是右边的):
- 比如说第4个(从1数起),其高度为2。显然,它的高度比左指针指向的柱子低,同时,它的宽度又变小了。因此,比当前左指针和当前右指针构成的容器,容量小
- 我们再可以选一个高的柱子来研究一下。比如倒数第三个。这个时候,纵使它很高(哪怕无穷大),但是由于木桶原理(短板决定)。容器的最大高度还是由右指针指向的柱子,决定。同样的,宽度还是变小了
因此,就和上期我讲的双指针类似(leetcode 167)。我们就可以排除当前的右指针所指向的柱子了。从而right—。继续去比较。
综上所述,我们就是不断的去比较左指针和右指针所指向的柱子高度。不断的排除掉矮的柱子。在遍历的过程中,得到最后的ans。
1 | class Solution { |
Leetcode 42
接雨水
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
再次借鉴leetcode的图:
嘶,我得画一下:
1. 前后缀分解
如图所示,假设说,我们要计算红色这个位置,可以盛放多少的水。我们就有三个考量:
- 左边最大的柱子高度是多少?这意味着,假设往红色的位置注水,左边最多能hold住多少的水
- 右边最大的柱子高度是多少?。。。
- 这个地方,柱子高多少?计算过1和2,这个地方理论上能放min(pre[i], suf[i])的水,但是需要排除掉这个柱子在底下所占的高度。pre[i]表示i这个位置,其左侧柱子最大高度;suf[i]表示i这个位置,其右侧柱子的最大高度。
解决第一个问题,我们可以构造一个pre最大数组:
1 | pre[0] = height[0]; |
同理,suf最大数组:
1 | suf[n - 1] = height[n - 1]; |
最后这个地方,i,可以放,min(pre[i], suf[i]) - height[i] 个水,加到最后的ans中
1 | for (int i = 0; i < n; i ++) { |
总的代码:
1 | class Solution { |
时间复杂度:O(n)
空间复杂度:O(n)
2. 双向双指针
上种做法的空间复杂度为O(n),观察到对于pre数组,随着指针增大,pre增大;对于suf数组,随着指针减小,suf减小。我们可以想想有没有什么办法把空间复杂度降下来??
如果说,我们有两个指针,一左一右。同时有,left_max和right_max两个变量。分别表示,left指向的位置,其左侧(包括left)最大的柱子高度;right指向的位置,其右侧(包括right)最大的柱子高度。
假设说:
- 若left_max < right_max:根据方法1,我们知道随着right—,right_max只会越来越大;随着left++,left_max也只会越来越大。因此对于当前left所指向的位置,其理论最多能乘放left_max个水,再减掉当前height[left]
- 同理。。不赘述,闭馆了
1 | class Solution { |
时间复杂度:O(n)
空间复杂度:O(1)