【力扣 Hot100】 刷题日记

D10 移动零

原题链接

方法一：原地栈

把nums数组当作栈，维护一个新的索引，把不为零的数据放到前面，最后再用0填满数组的剩余部分。

class Solution {
    public void moveZeroes(int[] nums) {
        int stackSize = 0;
        for (int num : nums) {
            if(num != 0){
                nums[stackSize] = num;
                stackSize++;
            }
        }
        Arrays.fill(nums, stackSize, nums.length, 0); //左闭右开
    }
}

复杂度：

• 时间复杂度：O(n) n为nums数组长度
• 空间复杂度：O(1)

方法二：双指针+交换元素

更优雅的方法。把0视作空位，可以把所有不为0的数字，放到数组左边的空位，交换位置之后，0就会全部集中到数组右边。

例如 nums=[0,0,1,2]，把 1 放到最左边的空位上，数组变成 [1,0,0,2]注意 1 移动过去后，在原来 1 的位置又产生了一个新的空位。也就是说，我们交换了 nums[0]=0 和 nums[2]=1 这两个数。

所以我们可以维护两个快慢指针，快指针遍历数组，慢指针记录0的位置，只要快指针指向非零数字，则交换快慢指针指向的数字，空位被填上，慢指针右移，这样就保证了所有非零元素都在数组的左侧。

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0; //用于标记0的位置
        for(int fast = 0; fast < nums.length; fast++){
            if(nums[fast] != 0){
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                slow++;
            }
        }

    }
}

盛水最多的容器

一个木桶能装多少水，取决于最短的那块木板，而不是最长的木板。

原题链接

这道题目是求哪两条线组成的容器存水最多。有什么方法可以遍历一次height就能得出最大值呢？

我们可以维护left和right指针，先计算一下这两个指针指向位置构成的容器大小，下一步是关键，判断如果height[left]大于height[right]，那么怎么操作才可能使得下一个容器大小大于当前值？让更矮的一侧向中间靠拢。

但是有人会说，木桶效应不应该是更小的高度决定容器大小吗，为什么要移动较小值的指针？

确实是这样，而且我们这么做并没有违背这个事实，因为我们移动较小值的指针是为了找到与较大高度更接近的较小值

这样即使缩短了横向距离，但是竖向距离仍可能变大，这样总面积可能更大。也就是说，如果height[left] >= height[right]，那么right--，如果height[left] < height[right]，那么left++。

这样下去，每次都会计算新的容器大小，直到left=right，结束，最大值也就找到了。

class Solution {
    public int maxArea(int[] height) {
        int left = 0; //左指针
        int right = height.length - 1; //右指针
        int maxN = 0; //最大面积
        while (left < right) {
            int s = 0;
            if (height[left] >= height[right]) {
                s = (right - left) * height[right];
                right--;
            } else {
                s = (right - left) * height[left];
                left++;
            }
            maxN = Math.max(s, maxN);
        }
        return maxN;
    }
}

这里代码的重复性比较高，其实可以抽取公共部分优化一下

class Solution {
    public int maxArea(int[] height) {
        int left = 0; //左指针
        int right = height.length - 1; //右指针
        int maxN = 0; //最大面积
        while (left < right) {
            int s = (right - left) * Math.min(right, left);
            if (height[left] >= height[right]) {
                right--;
            } else {
                left++;
            }
            maxN = Math.max(s, maxN);
        }
        return maxN;
    }
}

如果这篇文章对你有帮助，请点赞、评论、收藏，创作不易，你的支持是我创作的动力。