LeetCode刷算法题 - 11. Container Wit

写在前面:

程序员分两种，会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的，程序猿们都懂的，现在最权威流行的刷题平台就是 LeetCode。

LeetCode原题链接(英文)

LeetCode原题链接(中文)

string - C++ Reference

C++中int与string的相互转换

C++ Map常见用法说明

Question:

Difficulty:Medium Tag:Array

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.

Solution:

以下代码皆是本人用 C++写的，觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教，多多学习。

A1、暴力解法

粗暴进行循环遍历，问题复杂化，不可取
Time complexity : O(n^2)Time Limit Exceeded，代码如下

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        for (int i=0; i<height.size()-1; i++) {
            for (int j=i+1; j<height.size(); j++) {
                int area = std::min(height[i], height[j])*(j-i);
                maxArea = std::max(maxArea, area);
            }
        }
        return maxArea;
    }
};

A2、双指针解法

• 原则上需要遍历所有组成情况进行比较，如上双重循环遍历
• 若想减少遍历次数，必需排除一些情况的比较
• left、right 为数组左右边缘元素位置，此时 h 最大，两头指针向中间靠拢时 h 逐渐缩小
• 所以只有在 left 或 right 高度增大时面积才有可能怎能增大（其他高度小的情况可排除不必比较）

也就是以 height[0],height[n-1]的面积为基准，把所有情况分为大于此面积和小于此面积2种情况，然后把一定小于此面积的情况排除掉不用比较，只比较可能大于此面积的情况，提高了效率。

算法时间复杂度 O(n)，Runtime: 9 ms，代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间，可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0;
        int right = (int)height.size() - 1;
        while (left < right) {
            int h = min(height[left], height[right]);
            maxArea = max(maxArea, (right - left) * h);
            while (height[left] <= h && left < right) left++;
            while (height[right] <= h && left < right) right--;
        }
        return maxArea;
    }
};

引用相关

LeetCode 官网