OJ刷题总结 2

来源于：https://www.bilibili.com/video/BV1Qg411q7ia/?spm_id_from=333.999.0.0&vd_source=738644d63e97553d6e3dc1cd66a642d6

上次更新还是上周。。不是摆烂了，是这周实在是太忙碌了。。。最近科研不是很顺畅，复现个3dgs，环境配不好。。很奇怪。。。稍微看了点代码理解了一下。。。工作到晚上9点。。剩下时间，在图书馆学习下算法，写个总结。

Leetcode 11

盛最多水的容器

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

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

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

说明：你不能倾斜容器。

借鉴一下leetcode的例图：

假设说，我们有两个指针，一左一右。分别指向红色的两个柱子。

这个时候，我们选中红色柱子中的一个柱子，和矮的的柱子构成容器（也就是右边的）：

  • 比如说第4个（从1数起），其高度为2。显然，它的高度比左指针指向的柱子低，同时，它的宽度又变小了。因此，比当前左指针和当前右指针构成的容器，容量小
  • 我们再可以选一个高的柱子来研究一下。比如倒数第三个。这个时候，纵使它很高（哪怕无穷大），但是由于木桶原理（短板决定）。容器的最大高度还是由右指针指向的柱子，决定。同样的，宽度还是变小了

因此，就和上期我讲的双指针类似(leetcode 167)。我们就可以排除当前的右指针所指向的柱子了。从而right—。继续去比较。

综上所述，我们就是不断的去比较左指针和右指针所指向的柱子高度。不断的排除掉矮的柱子。在遍历的过程中，得到最后的ans。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int n = height.size();
        int left = 0, right = n - 1;
        while (left < right) {
            ans = max(ans, min(height[left], height[right]) * (right - left));
            if (height[left] <= height[right]) {
                left ++;
            }
            else 
                right --;
        }
        return ans;
    }
};

Leetcode 42

接雨水

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

再次借鉴leetcode的图：

嘶，我得画一下：

1. 前后缀分解

如图所示，假设说，我们要计算红色这个位置，可以盛放多少的水。我们就有三个考量：

  1. 左边最大的柱子高度是多少？这意味着，假设往红色的位置注水，左边最多能hold住多少的水
  2. 右边最大的柱子高度是多少？。。。
  3. 这个地方，柱子高多少？计算过1和2，这个地方理论上能放min(pre[i], suf[i])的水，但是需要排除掉这个柱子在底下所占的高度。pre[i]表示i这个位置，其左侧柱子最大高度；suf[i]表示i这个位置，其右侧柱子的最大高度。

解决第一个问题，我们可以构造一个pre最大数组：

1
2
3
4
pre[0] = height[0];
for (int i = 1; i < n; i ++) {
    pre[i] = max(pre[i - 1], height[i]);
}

同理，suf最大数组：

1
2
3
4
suf[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i --) {
    suf[i] = max(suf[i + 1], height[i]);
}

最后这个地方，i,可以放，min(pre[i], suf[i]) - height[i] 个水，加到最后的ans中

1
2
3
for (int i = 0; i < n; i ++) {
    ans += min(pre[i], suf[i]) - height[i];
}

总的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pre(n);
        vector<int> suf(n);
        pre[0] = height[0];
        for (int i = 1; i < n; i ++) {
            pre[i] = max(pre[i - 1], height[i]);
        }
        suf[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i --) {
            suf[i] = max(suf[i + 1], height[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            ans += min(pre[i], suf[i]) - height[i];
        }
        return ans;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

2. 双向双指针

上种做法的空间复杂度为O(n)，观察到对于pre数组，随着指针增大，pre增大；对于suf数组，随着指针减小，suf减小。我们可以想想有没有什么办法把空间复杂度降下来？？

如果说，我们有两个指针，一左一右。同时有，left_max和right_max两个变量。分别表示，left指向的位置，其左侧（包括left）最大的柱子高度；right指向的位置，其右侧（包括right）最大的柱子高度。

假设说：

  1. 若left_max < right_max：根据方法1，我们知道随着right—，right_max只会越来越大；随着left++，left_max也只会越来越大。因此对于当前left所指向的位置，其理论最多能乘放left_max个水，再减掉当前height[left]
  2. 同理。。不赘述，闭馆了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int premax = 0, sufmax = 0;
        int ans = 0;
        while(left <= right) {
            premax = max(premax, height[left]);
            sufmax = max(sufmax, height[right]);
            if (premax < sufmax) {
                ans += premax - height[left++];
            }
            else {
                ans += sufmax - height[right--];
            }
        }
        return ans;
    }
};

时间复杂度：O(n)

空间复杂度：O(1)