力扣热题100——一刷day02

力扣热题100——一刷day02"/>

力扣热题100——一刷day02

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、力扣11. 盛最多水的容器
• 二、力扣15. 三数之和
• 三、力扣42. 接雨水

前言

一、力扣11. 盛最多水的容器

采用双指针处理这道题目，面积res由两条边中最矮的那一条决定，从两端开始向内移动，每次只移动两条边种最矮的那一条，向内移动时，如果遇到比当前移动边更矮的总面积会减小，遇到更高的总面积可能会增大，如果，最大值在内部取到，那么最大值的最矮边一定大于外侧未移动的边，故最大值不会丢失

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

二、力扣15. 三数之和

同一个数组内取三个元素，三个元素互不相同，且取过的数不可以重复取，可对数组排序

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < nums.length - 2;){int left = i + 1, right = nums.length-1;if(nums[i]>0){return res;}while(left < right){int cur = nums[i] + nums[left] + nums[right];if(cur < 0){left ++;}else if(cur > 0){right --;}else{res.add(Arrays.asList(nums[i], nums[left], nums[right]));while(left < right && nums[left] == nums[left + 1])left++;while(left < right && nums[right] == nums[right-1])right--;left ++;right --;}}while(i < nums.length-2 && nums[i] == nums[i+1])i++;i ++;}return res;}
}

三、力扣42. 接雨水

class Solution {public int trap(int[] height) {int count = 0;Deque<Integer> deq = new LinkedList<>();deq.offerLast(0);for(int i = 1; i < height.length; i ++){if(height[i] < height[deq.peekLast()]){deq.offerLast(i);}else if(height[i] == height[deq.peekLast()]){deq.pollLast();deq.offerLast(i);}else{while(!deq.isEmpty() && height[i] > height[deq.peekLast()]){int index = deq.pollLast();if(deq.isEmpty()){break;}int left = deq.peekLast();int right = i;int high = Math.min(height[left], height[right]) - height[index];int len = right - left - 1;count += high * len;}deq.offerLast(i);}}return count;}
}