Leetcode 11

发布于 2020 年 09 月 30 日 | 更新于 2021 年 08 月 17 日

盛最多水的容器

题解 https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/

关键词： 数组 双指针

整体思路

用两个指针，从数组两头开始往中间靠拢，计算出遍历过程中最大的面积

我的思路

每次同时移动两个指针

  1. 对于左右两个指针，先分别找到下一个更高的新指针

  2. 计算三个面积：

    • 两个新指针分别与对面的旧指针之间i和nj j和ni
    • 两个新指针之间ni和nj
  3. 保留最大值
  4. 循环，两个指针重合时结束

规定移动限制

好像这样规定后，实际做的操作就和每次移动较矮的指针几乎一致。。。

（陷入了思维误区，遍历一遍n并不算暴力解法？）

题解思路

每次移动较矮的指针

  1. 较矮的指针，移动一格（感觉可以一次性移动到下一个更高的位置？）
  2. 计算面积
  3. 保留最大值
  4. 循环，两个指针重合时结束

总结

感觉就是自己想复杂了。。。同时移两边肯定比移一边更麻烦。仔细想想不管同时移几个，都是在相遇的时候停止，所以时间应该是一样的。所以每次移一边更容易理解和清晰地思考，也更容易实现。

每次移动一个较矮的指针在逻辑和编程方面更清晰，容易理解，而同时移动两个指针，就需要规定（设置）很多移动限制，相对来说理解和实现起来更复杂。然而两者的时间复杂度O(N)和空间复杂度O(1)都是一样的，因此后者更好。

代码

感觉测试样例不是固定的，相同代码多次提交运行时间差很多（8 ms，20 ms），内存消耗也有变化

// 我的代码
// 不知道为什么会超时！ 感觉时间复杂度也是O(N)吧
// 超时是因为犯了个低级错误，把stop_i的定义写在了循环里面。。。
// 推测超时原因：跑有序样例时，未记录stop_i，导致最大的那头指针反复遍历整个数组，造成超时
#include <iostream>
#include <vector>

using namespace std;

int get_area(int hi, int hj, int d)
{
    int h = hi < hj ? hi : hj;
    return h * d;
}

int main()
{
    vector<int> height;
    int tmp;
    while ( scanf("%d", &tmp) )
    {
        if ( !tmp ) break;
        height.push_back(tmp);
    }

    // begin
    int len = height.size();
    int i = 0;
    int j = len-1;
    int ans = 0;

    tmp = get_area(height[i], height[j], j-i);
    ans = tmp > ans ? tmp : ans;
    bool stop_i = false;
    bool stop_j = false;
    do
    {
        int ni = i;
        int nj = j;
        // bool stop_i = false;
        // bool stop_j = false;
        while ( !stop_i && ++ni < len && height[ni] <= height[i]);  // 找到下一个大于i的值
        while ( !stop_j && --nj >= 0 && height[nj] <= height[j]);  // 找到下一个大于i的值
        // 矮的一定能找到，高的不一定能找到
        // 如果能找到ni_j，则必定ni <= nj 反证法
        // if ( ni >= len || nj < 0 )
        // {
        //     if ( ni >= len ) stop_i = true;
        //     if ( nj < 0 ) stop_j = true;
        //     ni = ni >= len ? i : ni;
        //     nj = nj < 0 ? j : nj;
        //     tmp = get_area(height[ni], height[nj], nj-ni);
        //     ans = ans > tmp ? ans : tmp;
        // }

        if ( ni >= len )
        {
            stop_i = true;
            ni = i;
        }
        if ( nj < 0 )
        {
            stop_j = true;
            nj = j;
        }

        // 计算四个面积
        if ( !stop_i && !stop_j )
        {
            tmp = get_area(height[ni], height[nj], nj-ni);
            ans = tmp > ans ? tmp : ans;
        }
        if ( !stop_j )
        {
            tmp = get_area(height[i], height[nj], nj-i);
            ans = tmp > ans ? tmp : ans;
        }
        if ( !stop_i )
        {
            tmp = get_area(height[ni], height[j], j-ni);
            ans = tmp > ans ? tmp : ans;
        }

        if ( height[i] < height[nj] )
        {
            i = ni;
        }
        if ( height[j] < height[ni] )
        {
            j = nj;
        }
        if ( stop_i && stop_j ) break;
    } while ( i < j );
    // end

    printf("%d", ans);
    return 0;
}

// 题解代码
// 时间复杂度O(N) 遍历数组一次 （O(N)不算暴力吗。。。）
// 空间复杂度O(1) 常数级的空间（数组大小）
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
};