力扣热题100——一刷day02

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

---

前言

---

一、力扣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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二、力扣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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

三、力扣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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29