785 字

4 分钟

Day20260301

2026-03-01

Hot100

C++

/

Hot100

/

algorithm

Day20260301#

盛最多水的容器#

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

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

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

题解#

从暴力遍历的角度看，每个边界都会存在一个容纳水的值，一共有 $n*(n-1)/2$ 个边界。因此复杂度为 $O(n^2)$ 考虑（i，j）的边界，容水值为 $val_{ij}$ 若 height[i] < height[j] 显然对于 $val_{ik}$ 都不会大于 $val_{ij}$ 因此我们在枚举时改变j的值没有任何用，只需改变i的值即可。代码如下：

1
class Solution {
2
public:
3
    int maxArea(vector<int>& height) {
4
        int l = 0;
5
        int r = height.size()-1;
6
        int mx = 0;
7
        while(l<r){
8
            int tmp = min(height[l] , height[r]) * (r-l);
9
            mx = max(tmp,mx);
10
            if(height[l] > height[r]){
11
                r--;
12
            }else l++;
13
        }
14

15
        return mx;
16
    }
17
};

接雨水#

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

题解#

首先要想到对于 i 处的柱子接的雨水的量为左右两边比 i 高的最高柱子的较小值减去i的高度即为i处接雨水的量。然后就可以用动态规划的思路解决左右两边比 i 高的最高柱子。转移方程为 $dp[i] = max(dp[i+1],height[i+1])$ 左边同理代码如下：

1
class Solution {
2
public:
3
    int trap(vector<int>& height) {
4
        int dpL[height.size()];
5
        int dpR[height.size()];
6
        dpR[height.size()-1] = 0;
7
        for(int i=height.size()-2;i>=0;i--){
8
            dpR[i] = max(height[i+1],dpR[i+1]);
9
        }
10

11
        dpL[0] = 0;
12
        for(int i=1;i<height.size();i++){
13
            dpL[i] = max(height[i-1],dpL[i-1]);
14
        }
15

16
        int val = 0;
17
        for(int i=0;i<height.size();i++){
18
            int tmp = min(dpL[i],dpR[i]);
19
            val += max(0,tmp- height[i]);
20
        }
21

22
        return val;
23

24

25

26
    }
27
};

最大子数组和#

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

题解#

这个题是很经典的题目了。方法很多。首先是动态规划的方法，这个比较难想，记住就行。设f(i) 为以i结尾的最大连续数组，则对于f(i) 有转移方程 $f(i) = max(f(i-1)+nums[i],nums[i])$

然后计算出每个f(i) 最后求出f(i)的最大值即为答案。

1
class Solution {
2
public:
3
    int maxSubArray(vector<int>& nums) {
4
        vector<int> dp(nums.size());
5
        dp[0] = nums[0];
6
        for(int i=1;i<nums.size();i++){
7
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
8
        }
9
        int mx = dp[0];
10
        for(int i=0;i<nums.size();i++){
11
            mx = max(dp[i],mx);
12
        }
13

14
        return mx;
15

16
    }
17
};

第二种方法：使用前缀和+动态规划的方法。首先求出数组的前缀和。然后就可以发现，对于前缀和数组中，我们要找到两个数的差使之最大，并且较大值要在较小值后面。然后我们就可以定义两个数组，dpL[i] 与 dpR[i]。分别代表，i前最小值，和i后最大值。再动态规划求得这两个数组，最后遍历这两个数组，求取最大差值。

1
class Solution {
2
public:
3
    int maxSubArray(vector<int>& nums) {
4
        vector<int> pre;
5
        pre.resize(nums.size()+1);
6
        pre[0] = nums[0];
7
        for(int i=1;i<nums.size();i++){
8
            pre[i] = pre[i-1] + nums[i];
9
        }
10

11
        vector<int> dpR(nums.size());
12
        vector<int> dpL(nums.size());
13

14
        dpR[nums.size()-1] = pre[nums.size()-1];
15
        for(int i=nums.size()-2;i>=0;i--){
16
            dpR[i] = max(dpR[i+1],pre[i]);
17
        }
18
        dpL[0] = 0;
19
        for(int i=1;i<nums.size();i++){
20
            dpL[i] = min(dpL[i-1],pre[i-1]);
21
        }
22

23
        int mx = dpR[nums.size()-1];
24

25
        for(int i=0;i<nums.size();i++){
26
            int tmp = max(dpR[i]-dpL[i],dpR[i]);
27
            mx = max(tmp,mx);
28
        }
29

30
        return mx;
31

32
    }
33
};

Day20260301

https://blog.eachic.me/posts/hot100/day20260301/

作者

Eachic

发布于

2026-03-01

许可协议

CC BY-NC-SA 4.0

Day20260303

Day20260222