首页 > 其他分享 >[刷题班] LeetCode11. 盛最多水的容器

[刷题班] LeetCode11. 盛最多水的容器

时间:2024-01-14 16:23:38浏览次数:39  
标签:right int res height LeetCode11 最多水 left Math 刷题

题目描述

思路:左右指针

方法一:暴力,超出时间限制

模拟所有情况,记录最大的体积值。
体积 = Math.min(height[i], height[j]) * (j - i)

class Solution {
    public int maxArea(int[] height) {
        int res = Integer.MIN_VALUE;

        for (int i = 0; i < height.length; i ++) {
            for (int j = i + 1; j < height.length; j ++) {
                int edge = Math.min(height[i], height[j]);
                res = Math.max(res, (j - i) * edge);
            }
        }
        return res;
    }
}

时间复杂度O(n2)

方法二:双指针

思路

  • 初始化:双指针left和right分别位于水槽左右两端;
  • 循环收窄: 直至双指针相遇时跳出;
    • 更新面积最大值:res;
    • 选定两板高度中的短板,向中间收窄一格;
  • 返回值:返回面积最大值res即可;

木桶容量由短板决定, 移动长板的话, 水面高度不可能再上升, 而宽度变小了, 所以只有通过移动短板, 才有可能使水位上升.

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            int w = right - left;
            int h = Math.min(height[left], height[right]);
            res = Math.max(res, w * h);
            if (height[left] < height[right]) {
                left ++;
            } else {
                right --;
            }
        }
        return res;
    }
}

标签:right,int,res,height,LeetCode11,最多水,left,Math,刷题
From: https://www.cnblogs.com/keyongkang/p/17963840

相关文章

  • [刷题班] LeetCode27. 移除元素
    题目描述思路:快慢指针slow指针:其前面都是数值不等于val的元素。fast指针:用于遍历。方法一:classSolution{publicintremoveElement(int[]nums,intval){intslow=0,fast=0;for(;fast<nums.length;fast++){if(nums[fas......
  • [刷题班] LeetCode344. 反转字符串
    题目描述思路:左右指针方法一:classSolution{publicvoidreverseString(char[]s){intleft=0,right=s.length-1;while(left<right){chartemp=s[left];s[left]=s[right];s[right]=temp;......
  • [刷题班] LeetCode80. 删除有序数组中的重复项II
    题目描述思路:快慢指针slow指针指向已经处理元素的下一个位置因为数组有序,如果nums[fast]==nums[slow-2],那么nums[fast]肯定等于nums[slow-1],那么此时这个数就出现了三次。此时slow保持不变,fast继续遍历。关键:nums[fast]!=nums[slow-2]方法一:classSolution{......
  • [刷题班] LeetCode26. 删除有序数组中的重复项
    题目描述思路:快慢指针slow指针:指向已经处理的区域(没有重复元素)的最后一个位置fast指针:指向当前正在处理的元素方法一:classSolution{publicintremoveDuplicates(int[]nums){intslow=0,fast=0;for(;fast<nums.length;fast++){......
  • 刷题笔记——队列(C++)
    1696.跳跃游戏VI-力扣(LeetCode)给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。一开始你在下标 0 处。每一步,你最多可以往前跳 k 步,但你不能跳出数组的边界。也就是说,你可以从下标 i 跳到 [i+1,min(n-1,i+k)] 包含 两个端点的任意位置。你的目标是......
  • leetcode 11.盛最多水的容器
    leetcode11.盛最多水的容器第十一题:盛最多水的容器1.暴力枚举:会超时,但是做一些条件判断应该可以擦边过publicintmaxArea(int[]height){intmax_result=0;for(inti=0;i<height.length-1;i++){for(intj=i+1;j<height.length;j++......
  • 刷题笔记——栈(C++)
    LCR148.验证图书取出顺序-力扣(LeetCode)现在图书馆有一堆图书需要放入书架,并且图书馆的书架是一种特殊的数据结构,只能按照 一定 的顺序 放入 和 拿取 书籍。给定一个表示图书放入顺序的整数序列 putIn,请判断序列 takeOut 是否为按照正确的顺序拿取书籍的操作序列。你可......
  • 刷题笔记——单向链表(C++)
    206.反转链表-力扣(LeetCode)给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。解题思路三指针。temp指针用于存储当前节点的下一节点,pre指针用于存储当前节点反转后指向的新节点。具体操作如下:反转过程:代码实现classSolution{public:ListNode*reverseList(Li......
  • 刷题笔记——顺序表(C++)
    665.非递减数列-力扣(LeetCode)给你一个长度为 n 的整数数组 nums ,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的: 对于数组中任意的 i (0<=i<=n-2),总满足 nums[i]<=nums[i+1]。解题思路遍历数组,计算递......
  • 力扣11-盛最多水的容器
    难度:【中等】题目给画了图,比较方便理解。第一个思路是把所有的面积都计算一遍,显然时间复杂度很高;接着思考第二个方法,使用双指针,通过移动首尾指针来计算面积:如果下一个height超过当前值,就移动该指针,直到两个指针相遇。写完代码运行超时。超时是因为死循环了,因为上面的移动指针的......