做题记录_(210203)

2021-02-03

2021/02/03做题记录

依旧是数组的题，这次使用的是双指针的方法

老规矩我们先看一下题：

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

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

示例 2：
1
2
输入：height = [1,1]
输出：1
示例 3：
1
2
输入：height = [4,3,2,1,4]
输出：16
示例 4：
1
2
输入：height = [1,2,1]
输出：2
然后我们看一下题中给的默认代码

1
2
3

int maxArea(int* height, int heightSize){
    
}

简单分析一下，不难得知 height 是那个数组， heightSize 是数组大小，通过实例中的数据我们演草一下，很容易就发现了规律：所计算面积就是两个坐标下标的差和下标对应的数较小的那一个的乘积。最简单也是最容易想的方法就是暴力枚举，将所有组合都算一遍，一定可以得到一个最大面积的解，但显然不是题目想要的。

进一步分析，那我们不妨采用双指针的方法，从两头分别开始遍历，同时利用一个额外的变量存储每次计算的值，那么也依旧可以算出最小的那一个。

先给出我的代码如下：

int maxArea(int* height, int heightSize){
    int left = 0;
    int right = heightSize - 1;
    int maxArea = 0;
    while( left != right )
    {
        if(height[left] < height[right])
        {
            maxArea = maxArea > height[left]*(right-left) ? maxArea : height[left]*(right-left);
            left++;
        }
        else
        {
            maxArea = maxArea > height[right]*(right-left) ? maxArea : height[right]*(right-left);
            right--;
        }
    }
    return maxArea;
}

使用了三目运算符，结构上更容易看懂。

简单分析一下为什么当 height[left] < height[right]条件成立时，最后将 left 指针左移 left++一定可以得到最优解，其实道理也简单，假设当前左右指针指向了两条线，右面的线（right）高，那么如果令 right--，那么所得结果计算矩形面积时底边一定是在减少，高可能不变（即right--后指向的新边比之前的高），也有可能降低（即right--后指向的新边比之前的低），那么面积在这样的情况下一定是减少的，所以只有令left++所得结果才有可能向更大值遍历。

上一次使用双指针好像是大二数据结构课堂上，讲到排序时使用的，这道题是我第一次在课堂之外用到了课堂内所学算法思想。

也算学有所成（大概吧）