【数组】 11. 盛最多水的容器

之前立了flag说这个学期要写技术blog,正好今日喜迎国庆,值此佳节,实乃开启撰写技术博客之旅的好时机。同时,我也希望能与广大CSDNer进行技术交流并获得指导。那么,就从第一篇文章开始吧!

刷题思路

首先简单规划一下准备刷力扣的思路,在参考了若干大佬的文章后,我准备按照 数组→链表→二叉树/树→二分查找→BFS/DFS 的顺序进行刷题。每种类型的题目先刷5-10题,对刷题有个初步的了解以后再进行更深入的刷题。

(算法虐我千百遍,我待算法如初恋。希望能享受在算法的海洋里遨游的过程~)

刷题随想

数组专题做的第一道题其实是twoSum,但感觉好像能写的不多,主要就两种思路:

  1. 双重for循环遍历,找到加和符合target的两个数就break。
  2. 运用基于红黑树的map映射(个人将map与python里的字典做类比),通过遍历一遍或两遍hash表实现。

做的第二题是第11题:盛最多水的容器

【数组】 11. 盛最多水的容器

这道题目实质上是算面积。由于没有任何经验,因此刚开始拿到题目的第一思路就是穷举。后来想了一下,这种方法其实也可以称为双指针(双索引)嘛,只不过两个指针扫描的方向和出发的位置都一毛一样而已:双重for循环,算出所有area,不断更新并记录max area。

但这个算法复杂度就是【数组】 11. 盛最多水的容器了,有点可怕。。。


又想了大概10min,依然想不到什么好的思路,便去看了下题解。当点开官方题解,看到“双指针”三个字,以及简要描述后,我一瞬间感觉被闪电击中,思路一下就被激发了:

设置一左一右两个指针(索引)。因为面积的计算公式是:min(height[l],height[r])*(r-l),因此我们每次移动数组元素值较小(height[l]或height[r])的元素的指针;且移动时,l每次往右移动一位,r往左移动一位。这样能在l和r之间的距离缩小的同时,更新min(height[l],height[r])的值。不断重复这个过程,算出每一个area,并更新记录max area的值。此时,仅需扫描一遍数组即可,时间复杂度降为了【数组】 11. 盛最多水的容器

后来,我发现移动左/右指针的过程与快排中的颇为类似。因此,我又优化了一下代码,把

for(int i=0;i<height.size();i++)

改成了

while(l!=r)

这样,执行时间从76ms降到了60ms,超过了约98%的提交者~

最后,附完整代码如下:

//双指针解法
//T:O(n) S:O(1)
class Solution {
public:
    int maxArea(vector<int>& height) {  
        int l=0,r=height.size()-1;
        int ma=0;
        while(l!=r)
        {
            int tmp=min(height[l],height[r])*(r-l);
            if(tmp>ma) ma=tmp;
            if(height[l]<height[r]) l++;
            else r--;
        }
        return ma;
    }
};

上一篇:【数据结构】Robot area 机器人运动范围


下一篇:计算矩形面积