数组：双指针

0011. 盛最多水的容器 (opens new window)

题目

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

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

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

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

解析

使用首尾双指针，具体过程如下：

• 求出当前双指针对应的容器的容量；
• 由于对应数字较小的那个指针以后不可能作为容器的边界了，将其丢弃，并移动对应的指针。

代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int l = 0, r = height.size() - 1;
        while (l < r) {
            ans = max(ans, min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) ++l;
            else --r;
        }
        return ans;
    }
};

func maxArea(height []int) (ans int) {
    l, r := 0, len(height)-1
    for l < r {
        ans = max(ans, min(height[l], height[r])*(r-l))
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        l, r = 0, len(height) - 1
        while l < r:
            ans = max(ans, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

0026. 删除有序数组中的重复项 (opens new window)

题目

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解析

在遍历数组的同时，通过用一个辅助下标记录最后一个不重复元素的位置，遍历结束时，辅助下标的值就代表不重复数组的长度，直接返回即可。

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        int idx = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[idx]) {
                nums[++idx] = nums[i];
            }
        }
        return idx + 1;
    }
};

0027. 移除元素 (opens new window)

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解析

本题与 0026. 删除有序数组中的重复项 解法相似，只是循环中的赋值条件发生了改变。

本题不需要和去重元素相比，只要和给定的 val 相比即可。

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int idx = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[idx++] = nums[i];
            }
        }
        return idx;
    }
};

0042. 接雨水 (opens new window)

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解析

木桶原理，从当前节点往左找最高的高度，往右找最高的高度，这两个高度我们可以看做是木桶的两个木板，能接的雨水由最短的那块决定，累加每个位置能存的雨水量即可。

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0, lmax = 0, rmax = 0;
        while (l < r) {
            lmax = max(lmax, height[l]);
            rmax = max(rmax, height[r]);
            if (lmax < rmax) {
                ans += lmax - height[l];
                l++;
            } else {
                ans += rmax - height[r];
                r--;
            }
        }
        return ans;
    }
};

0080. 删除排序数组中的重复项 II (opens new window)

题目

给你一个有序数组 nums，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

解析

本题与 0026. 删除有序数组中的重复项 解法相似，只是循环中的赋值条件发生了改变。

由于允许每个元素最多出现两次，因此在循环中需要判断：只要当前元素和结果数组的倒数第二个元素不同就可以加入。

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2) return nums.size();
        int idx = 1;
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] != nums[idx - 1]) {
                nums[++idx] = nums[i];
            }
        }
        return idx + 1;
    }
};

0487. 最大连续1的个数 II (opens new window)

题目

给定一个二进制数组，你可以最多将 1 个 0 翻转为 1，找出其中最大连续 1 的个数。

解析

这里用一个通用解法，若允许翻转 k 个 0，求最大连续 1 的个数。

使用一个队列存储已遍历元素的 0 的位置，当队列长度超过 k 时，则进行 pop 操作，每次循环更新最大长度。

代码

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int ans = 0;
        int k = 1;  // 通用方法，最多可翻转 k 个 0
        queue<int> q;
        for (int i = 0, l = 0; i < nums.size(); i ++) {
            if (nums[i] == 0) {
                q.push(i);
            }
            if (q.size() > k) {
                l = q.front() + 1;
                q.pop();
            }
            ans = max(ans, i - l + 1);
        }
        return ans;
    }
};

0581. 最短无序连续子数组 (opens new window)

题目

给你一个整数数组 nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

解析

同时从前向后和从后向前遍历，分别得到要排序数组的右边界和左边界。

• 寻找右边界：从前向后遍历的过程中，用 max 记录遍历过元素的最大值，若当前元素小于 max，则更新右边界；
• 寻找左边界：从后向前遍历的过程中，用 min 记录遍历过元素的最小值，若当前元素大于 min，则更新左边界。

说明

• 右边界的定义：右边界的左边一定存在一个比右边界大的数，导致它不配在右边界这个位置；
• 左边界的定义：左边界的右边一定存在一个比左边界小的数，导致它不配在左边界这个位置。

代码

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int len = nums.size();
        int start = 0, end = -1;
        int max = nums[0], min = nums[len - 1];
        for (int i = 0; i < len; i ++) {
            if (nums[i] < max) {
                end = i;
            } else {
                max = nums[i];
            }
            if (nums[len - i - 1] > min) {
                start = len - i - 1;
            } else {
                min = nums[len - i - 1];
            }
        }
        return end - start + 1;
    }
};