当前位置：首页 > article >正文

【OJ刷题】双指针问题3

article 2024/11/15 6:33:41

这里是阿川的博客，祝您变得更强

✨ 个人主页：在线OJ的阿川
💖文章专栏：OJ刷题入门到进阶
🌏代码仓库：

写在开头

现在您看到的是我的结论或想法，但在这背后凝结了大量的思考、经验和讨论

在这里插入图片描述

1. 题目介绍

难度：中
题目练习：盛最多水的容器
题目信息：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。
举个例子： 具体如图1所示

图1 举个例子

2. 题目拆解

本质上：观察规律，利用单调性
特点是：在组合搭配中有一定单调性规律
解决方法：双指针算法，如图2所示

图2 双指针

3. 具体详情

1.定义两个指针和一个最大值，一个指向最左边，一个指向最右边
2. 先算出一个体积v，两个指针的所指的线，谁比较小谁移动
3.每算出一个容积，更新一下最大值
4.两个指针相遇则停止

4. 具体代码

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        // 谁小谁移动，返回最大体积
        int left = 0, right = height.size() - 1, max_column = 0;
        while(left < right)
        {
            int v = min(height[left], height[right]) * (right - left);
            max_column = max(max_column, v);
            if(height[left] > height[right]) right--;
            else left++;
        }
        return max_column;
    }
};