Container With Most Water

Description

Given n non-negative integers a₁, a₂, …, a₂, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

思路

这道题让我想起了木桶效应Buckets effect，一只水桶能装多少水取决于它最短的那块木板，好像最近Elon Musk给他员工的信里面也有提，BTW，今天下午要试驾Model S啦好开心，机缘巧合机缘巧合…
咳咳，不过这道题目要求的是两块木板能组成的最大面积，如下图。 bucket container 可以看到，最大组成面积不仅仅由最短的“木板”决定，同时，两块木板的距离越长，自然组成的面积也会越大。这么一来，除了遍历使用复杂算法还有什么别的方式吗？毫无疑问，这是存在的。我们虽然不能“预测”，接下来选择的木板的长短，但是，我们可以使得距离长度由最长递减，期间不断的变化头部指针或者尾部指针的指向来递减长度。显而易见的，在变化头指针还是尾指针的选择上，我们需要执行一个固定的策略来确保决策的必要性。现在，假设我们变化的是指针中所指的较大值的那个，那么可以预见，这并不能改变现有的最小值，然而面积是由最小值和长度决定，所以，当我们寻迹缩小长度的同时，我们需要改变现有head和tail中较小的那个指针来尽力使得这次长度的减小被值所“弥补”。有了这个基本算法思想，接下来的事情就水到渠成了。

Solution

#include <algorithm>  
#include <vector>  
using namespace std;  
class Solution
{
  public:
    int maxArea(vector<int> &height)
    {
        int maxarea = 0, area = 0, r = height.size() - 1;
        int *head = &height[0];
        int *tail = &height[r];
        int l = tail - head;
        while (l)
        {
            area = min(*head, *tail) * (tail - head);
            maxarea = max(maxarea, area);
            if (*head < *tail)
                head++;
            else
                tail--;
            l--;
        }
        return maxarea;
    }
};

小结

最近放弃了用python刷题，改学了C++。都说刷算法就应该用c++或者java，可以加强对于思维的锻炼。但是我使用C++并不是因为上述缘由。
上大一的时候就学过c，但是那个时候实在被学校破电脑上的idle界面丑哭，之后转了专业之后也不怎么使用c，反而用matlab仿真各种东西更方便些，一条工具箱函数的不归路啊…后来接触到的也只是自己偶然中遇到的python了。当然，那个时候我还一直以为自己学CT就是要进运营商了，还不知道更好的选择会有那么多，所以想法随着眼界还是会变化挺多的。一直都有学习C++的想法，但是由于各种原因没有持续的付出努力，我想一方面是由于那时候智力和意志都没有完全成熟吧，难以入门，也有很多眼前的事情需要做，就一拖再拖。后来就到了今年的清明节，晕晕乎乎的就拿起来了C++ primer看了起来，看了些基本的东西之后，就大概看了看一个gitbook《高速上手C++14》，觉得还蛮有意思，在这段时间，我也配置好了我的C++开发环境，也就是mingw+vscode，轻量级编译器和高颜值文本编辑器，慢慢也就上手了吧。
最近也学了计划列表中的一些东西，总觉得要是不趁着年轻脑子还好用的时候多学些东西，年纪大了总会有遗憾的吧，嗯…不留白，就这样。

T11. Container With Most Water

Container With Most Water

Description

思路

Solution

小结

CATALOG

FEATURED TAGS

FRIENDS