首页 > 其他分享 >LeetCode11. 盛最多水的容器题解

LeetCode11. 盛最多水的容器题解

时间:2024-06-24 12:53:31浏览次数:20  
标签:right int 题解 height LeetCode11 ans 最多水 left

LeetCode11. 盛最多水的容器题解

题目链接:

https://leetcode.cn/problems/container-with-most-water

示例

思路

暴力解法

定住一个柱子不动,然后用其他柱子与其围住面积,取最大值。

代码如下:

public int maxArea1(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 area = Math.min(height[i], height[j]) * (j - i);
            ans = Math.max(ans, area);
        }
    }
    return ans;
}

此方法的时间复杂度为O(n^2),很显然太慢。我们需要想其他的思路。

对撞指针

暴力解法的搜索空间如下

那么我们是否可以缩小搜索空间呢?

以第一行为例,高度限制为1了,那么我们只需要看宽度最大的地方即可,第一行搜索空间中所有灰色的都不用看了;

以第二行为例,我们不止要看宽度最大的地方,因为height[right]会变大,所以我们只需要看第二行图中三个即可。

以此类推;

我们定义:

left为数组开始位置;

right为数组结束位置;

初始化所求最大面积为result = 0;

  1. 计算result = Max(result,left和right之间围成的面积);
  2. 如果height[left] <= height[right]:left++;
  3. 如果height[left] > height[right]:right--;
  4. 直到left > right;

代码如下

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) return 0;

        int left = 0, right = height.length - 1;
        int result = 0;

        while (left < right) {
            //计算面积
            result = Math.max(result, Math.min(height[left], height[right]) * (right - left));
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return result;
    }
}

标签:right,int,题解,height,LeetCode11,ans,最多水,left
From: https://www.cnblogs.com/nicaicai/p/18264826

相关文章

  • [题解]CF1716D Chip Move
    思路Part1这种题目应该能一眼看出是DP。我们令\(dp_{i,j}\)表示走到\(j\)这个位置,最后一步花了\(i\)的倍数。那么,我们的方程就很好想了:\(dp_{i,j}=\sum_{k=1}^{j-k\timesi\geq0}dp_{i-1,j-k\timesi}\)。因为,我们走到\(j\)的位置只能走\(i\)的倍......
  • [题解]CF1714F Build a Tree and That Is It
    思路由于题目中说这是一棵无根树,不太方便思考,于是,我们可以假装把这棵树看做有根树。首先我们令\(d_1,d_2,d_3\)分别表示从根节点到节点\(1,2,3\)的长度(不算相交部分)。那么我们可以得到下式:\[\left\{\begin{matrix}d_{12}=d_1+d_2\\d_{13}=d_1+d_3\\......
  • [题解]CF1712E1 LCM Sum (easy version)
    思路这是一道极好的思维题,主要考察了:组合数学和正难则反的方法。这题可以发现如果用直接法将十分的繁琐,于是乎,我们可以用正难则反的方法,即:总的减去不满足的。这道题总的很好求,为:\(C_{r-l+1}^{3}\)。不满足的情况,我们就可以将题目转化为:\(\operatorname{lcm}(i,j,k)<i+......
  • [题解]CF1712D Empty Graph
    思路因为我们枚举的直径是具备单调性的,所以可以使用二分答案。我们可以想一个事情,如果有两个点\(u\)和\(v\),它们两点之间的最短路径要么是直接从\(u\tov\);要么是经过一个中转点\(t\),即:\(u\tot\tov\)。然后,我们可以发现一个显然的规律,就是\(t\)一定是区间\(a\)中......
  • [题解]CF1704D Magical Array
    题意给定\(n\)个长度为\(m\)的数组,对于每一个数组选择下面任意一种操作进行若干次(操作二只能被一个数组选出)。\(c_{t,i}-1,c_{t,i-1}+1,c_{t,j}-1,c_{t,j-1}+1\)。\(c_{t,i}-1,c_{t,i-1}+1,c_{t,j}-1,c_{t,j-2}+1\)。最后输出选择操作二的数组......
  • [题解]CF1665E MinimizOR
    思路发现\(2^k\)大的数,最终的答案一定由前\(k+1\)小的元素组成。考虑数学归纳法,显然当\(k=1\)成立。假令\(k'\)时成立,证明\(k=k'+1\)时成立即可:若第\(k\)位有两个及以上的\(0\),显然最终答案的第\(k\)位一定为\(0\),因此考虑前面的\(k-1\)位,显然取......
  • [题解]CF1473D Program
    思路因为此题目中对于数的更新只能为\(1\),所以,如果我们找到了\([1,l-1]\)与\([r+1,n]\)中能获得的两个极值即可。我们为\(S\)赋予权值,用一个数组\(a\)储存:如果\(S_i\)为+,则其权值为\(1\)。否则其权值为\(-1\)。那么,在第\(i\)次操作后,能产生的数是\(\s......
  • [题解]CF1312E Array Shrinking
    思路本题为P3146变式,也算是一道很经典的区间DP题了。因为\(n\leq500\),考虑区间DP。定义\(dp_{i,j}\)表示操作\([i,j]\)区间剩余长度的最小值。那么,我们可以枚举一个中间值\(k\),可以显然地得到一个状态转移方程(即不能合二为一的情况):\[dp_{i,j}=\min(dp_{i,......
  • [题解]CF1223F Stack Exterminable Arrays
    CCF出的原题观摩一下。思路首先可以用一个Trie来维护。在这里对本文中的一些变量做一下说明。\(p\)表示当前维护的Trie中,指向的元素编号。\(t_i\)表示在Trie中编号为\(i\)的元素在原序列中的值。\(f_i\)表示在Trie中编号为\(i\)的元素在Trie中的父节点。......
  • [题解]CF1175E Minimal Segment Cover
    思路这是一道简单的DP题,DP题的核心就是状态转移。先来说一说\(dp\)数组的含义。\(dp_{i,j}\)表示从\(i\)这个点用\(2^j\)条线段能走到的最远的点。我们再来考虑一下边界情况。因为我们只用\(2^0\)条线段,那么:\(dp_{i,0}=\max(dp_{i,0},r)\)接着,我们递推一......