LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)

简介: LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)



一、编程题:167. 两数之和 II - 输入有序数组(双指针)

1.题目描述

  给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明:你不能倾斜容器。 LeetCode题目链接。

2.示例1:

输入:[1,8,6,2,5,4,8,3,7]

输出:49

解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

3.示例2:

输入:height = [1,1]

输出:1

4.提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

二、解题思路

这次还是老规矩练习一下双指针的思想,不枉练习这么多次双指针的题,现在双指针思路算是有一点长进了。其关键点还是该怎么去移动这两个指针?这一点要理清楚。;

1.思路

解决方法1(个人想法):

  • Step 1.创建left,right分别指向数组开头和末尾,并用maxsun存储数组中得到的最大水量;
  • Step 2.通过比较height[left]和height[right]大小来决定指针的移动,当height[left]<height[right]时,要保持大的一边不动,小的一边移动到下一个元素(left++);
  • Step 3.同理当height[left]>height[right]时,右指针移动到下一位(right–);
  • Step 4.重复Step2,3步直到遍历完整个数组就能得到最大水量;

这里Step2,3步的移动时是通过贪心思想来进行的,原理上两边需要不断的向大的高度去取,就有可能会得到其最优解。

2.复杂度分析:

时间复杂度 O(N): 双指针遍历一次底边宽度N。

空间复杂度 O(1): 使用常数额外空间。


三、代码实现

。每个代码块都写了注释,方便理解,代码还可以改进;

代码如下(示例):

解法一:

class Solution {
    public int maxArea(int[] height) {
        //方法一
        int left = 0, right = height.length - 1, maxsum = 0, sum, w;
        while(left < right){
            w = right - left;
            // 两者进行比较,谁小谁先移动,直到遍历完整个数组
            if(height[left] < height[right]){
                sum = (w) * height[left++];
                maxsum = Math.max(maxsum, sum);
            }else{ 
                sum = (w) * height[right--];
                maxsum = Math.max(maxsum, sum);
            }
        }
        return maxsum;
    }
}

提交结果:


总结

以上就是今天要讲的内容,做题的时候,就是奔着双指针的思路进行解决的,联练习这么多次现在逐渐找到了点感觉。我感觉就是双指针的关键点就是在于该怎么去移动两个指针,理清这一点之后离结果也就不远了,以前不懂的时候做一题就花费一天,现在一个上午就完事了,很明显有了提示。所以就赶紧记录一下这时刻。

感谢观看,如果有帮助到你,请给题解点个赞和收藏,让更多的人看到。🌹 🌹 🌹

也欢迎你,关注我。👍 👍 👍

原创不易,还希望各位大佬支持一下,你们的点赞、收藏和留言对我真的很重要!!!💕 💕 💕 最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!


相关文章
|
5天前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
5天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0
|
5天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
12 0
|
5天前
|
算法
【刷题】 leetcode 面试题 08.05.递归乘法
递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。
25 4
【刷题】 leetcode 面试题 08.05.递归乘法
|
5天前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
27 5
【刷题】 leetcode 面试题 01.06 字符串压缩
|
5天前
|
存储 算法 测试技术
|
5天前
|
算法 C语言 C++
|
5天前
|
监控 Kubernetes Docker
【Docker 专栏】Docker 容器内应用的健康检查与自动恢复
【5月更文挑战第9天】本文探讨了Docker容器中应用的健康检查与自动恢复,强调其对应用稳定性和系统性能的重要性。健康检查包括进程、端口和应用特定检查,而自动恢复则涉及重启容器和重新部署。Docker原生及第三方工具(如Kubernetes)提供了相关功能。配置检查需考虑检查频率、应用特性和监控告警。案例分析展示了实际操作,未来发展趋势将趋向更智能和高效的检查恢复机制。
【Docker 专栏】Docker 容器内应用的健康检查与自动恢复
|
3天前
|
Java 虚拟化 Docker
Docker简介及用途,为什么要使用Docker?Docker容器和虚拟机的区别
Docker简介及用途,为什么要使用Docker?Docker容器和虚拟机的区别

热门文章

最新文章