Leetcode Hot 100之四：283. 移动零+11. 盛最多水的容器

283.移动零

题目：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

思路：

使用双指针i和j。第一遍遍历i从左到右遍历数组，遇到非零元素即赋值给j所在的位置。因为j的数量一方面等于非零元素的个数，另一方面等于最终形态数组的左边最后一个非零元素的下标-1。（相当于一个数组长度是4，最后一个元素的下标就是4-1，为3）
第二遍再从j下标开始遍历，一直到数组结尾，都赋值为0，即相当于从最终形态数组的左边最后一个非零元素的下一个，即零元素一直到数组结尾，都赋值为0.

java代码：

class Solution {
    public void moveZeroes(int[] nums) {
       int len=nums.length;
       if(nums == null||len==0) return;
        int j=0;
        for(int i=0;i<len;i++){
            if(nums[i]!=0){
                nums[j++]=nums[i];
            }
        }
        for(int i=j;i<len;i++)nums[i]=0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

效率：

时间上为1ms，击败了99%的用户。不用再优化了。

11.盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

思路

暴力做法：从左到右遍历，每次都固定左边界，然后再从左边界开始遍历右边界。这样可以涵盖所有面积的情况。但是因为是双重循环，所以时间复杂度为O（N）。

双指针做法：针对这种两边边界都会移动的情况下，我们优化时首先需要考虑的就是双指针。暴力循环的做法，每次固定左边界，右边界移动，会让底和高同时变化。这样就让我们无法提前判断是否某些情况是无需遍历的，可以被优化的。基于此，我们要思考的就是如何移动，能只有一个因素影响面积。
我们发现，如果不是固定左边界，然后右边界从左边界处从左到右遍历。而是左右边界都各自放在坐标的左右边界，这样就确保了移动的过程中底是越来越小的，只有高变化时才有可能出现面积更大的可能。那么就只有一个因素影响面积。
接下来我们需要判断什么时候移动左边界，什么时候移动右边界。同理，我们只需要移动高度较小的那边。因为高度较小的那边限制了面积，只有移动他才有可能出现面积更大的情况。
这个题力扣官方讲解的很好，建议还是不明白的话去看下官方讲解视频。

java代码

class Solution {
    public int maxArea(int[] height) {
        int len=height.length;
        int ans=0;
        int i=0;
        int j=len-1;
        while(j>i){
            int mmin=Math.min(height[i], height[j])*(j-i);
            ans=Math.max(ans, mmin);
            //考虑移动左指针还是右指针
            //如果左指针的高度比右指针小，那么此时移动左指针才有可能找到面积更大的区域
            if(height[i]<height[j]){
                //移动左指针
                i++;
            }else j--;
        }
         return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

效率

4ms，击败 61.80%使用 Java 的用户，还行，没啥需要优化的空间了。