乐趣区

关于java:每日算法刷穿-LeetCode11-盛最多水的容器中等

点击 这里 能够查看更多算法面试相干内容~

题目形容

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线,垂直线 i 的两个端点别离为 (i, ai)(i, 0)。找出其中的两条线,使得它们与 x 轴独特形成的容器能够包容最多的水。

阐明:你不能歪斜容器。

示例 1:

 输出:[1,8,6,2,5,4,8,3,7]
输入:49 
解释:图中垂直线代表输出数组 [1,8,6,2,5,4,8,3,7]。在此状况下,容器可能包容水(示意为蓝色局部)的最大值为 49。

示例 2:

 输出:height = [1,1]
输入:1

示例 3:

 输出:height = [4,3,2,1,4]
输入:16

示例 4:

 输出:height = [1,2,1]
输入:2

提醒:

  • n = height.length
  • 2 <= n <= 3 * 104
  • 0 <= height[i] <= 3 * 104

奢侈解法

咱们能够间接枚举所有的状况:先枚举确定左边界,再往右枚举确定右边界。

而后再记录枚举过程中的最大面积即可:

class Solution {public int maxArea(int[] height) {
        int n = height.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {
                int w = j - i;
                int h = Math.min(height[i], height[j]);
                ans = Math.max(w * h, ans);
            }
        }
        return ans;
    }
}

工夫复杂度:$O(n ^ 2)$

空间复杂度:$O(1)$


双指针 + 贪婪解法

先用两个指针 ij 指向左右边界,而后思考指针应该怎么挪动。

因为形成矩形的面积,取决于 ij 之间的间隔(记为 w)和 ij 下标对应的高度的最小值(记为 h)。

首先无论是 i 指针往右挪动还是 j 指针往左挪动都会导致 w 变小,所以想要可能枚举到更大的面积,咱们应该让 h 在指针挪动后变大。

无妨假如当前情况是 height[i] < heigth[j](此时矩形的高度为 height[i]),而后分状况探讨:

  • ij 两者高度小的指针挪动,即 i 往右挪动:

    • 挪动后,i 指针对应的高度变小,即 height[i] > height[i + 1]wh 都变小了,面积肯定变小
    • 挪动后,i 指针对应的高度不变,即 height[i] = height[i + 1]w 变小,h 不变,面积肯定变小
    • 挪动后,i 指针对应的高度变大,即 height[i] < height[i + 1]w 变小,h 变大,面积可能会变大
  • ij 两者高度大的指针挪动,即 j 往左挪动:

    • 挪动后,j 指针对应的高度变小,即 height[j] > height[j - 1]w 变小,h 可能不变或者变小(当 height[j - 1] >= height[i] 时,h 不变;当 height[j - 1] < height[i] 时,h 变小),面积肯定变小

      • 挪动后,j 指针对应的高度不变,即 height[j] = height[j - 1]w 变小,h 不变,面积肯定变小
      • 挪动后,j 指针对应的高度变大,即 height[j] < height[j - 1]w 变小,h 不变,面积肯定变小

综上所述,咱们只有将高度小的指针往内挪动,才会枚举到更大的面积:

class Solution {public int maxArea(int[] height) {
        int n = height.length;
        int i = 0, j = n - 1;
        int ans = 0;
        while (i < j) {ans = Math.max(ans, (j - i) * Math.min(height[i], height[j]));
            if (height[i] < height[j]) {i++;} else {j--;}
        }
        return ans;
    }
}

工夫复杂度:会对整个数组扫描一遍。复杂度为 $O(n)$

空间复杂度:$O(1)$


最初

这是咱们「刷穿 LeetCode」系列文章的第 No.11 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先将所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

因为 LeetCode 的题目随着周赛 & 双周赛一直减少,为了不便咱们统计进度,咱们将依照系列起始时的总题数作为分母,实现的题目作为分子,进行进度计算。以后进度为 11/1916

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:Github 地址 & Gitee 地址。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其余的优选题解。

算法与数据结构
LeetCode 题解
算法面试
退出移动版