• 缩减搜索空间
  • 11. 盛最多水的容器
    • 题目描述
    • 分析与题解
  • 167. 两数之和 II
    • 题目描述
    • 分析与题解
  • 240. 搜索二维矩阵 II
    • 题目描述
    • 分析与题解

缩减搜索空间

笔者先通过描述第一道简单的例题后，对算法进行详细的剖析。

11. 盛最多水的容器

题目描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画n条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和(i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例：

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

提示：

• n = height.length
• 2 <= n <= 3 * 104
• 0 <= height[i] <= 3 * 104

分析与题解

最简单粗暴的方法肯定是暴力枚举所有可能的组合，使用for循环嵌套即可实现，需要注意下标的范围选择，大致框架如下：

for (int i = 0; i < height.size()-1; i++) {
	for (int j = i+1; j < height().size(); j++){
		// 详细讨论代码
	}
}

小心嵌套下标不能重合，并且对于外层下标进行一位的缩减即可，因为不是本章重点不再深入讨论。

上述方法可以预见算法复杂度为O(n^2)，执行效率并不理想。我们尝试使用双指针实现缩减搜索空间的策略，要点在于指针每移动一次，都意味着排除掉了一根柱子。可能刚开始理解起来比较抽象，这里以一个小例子帮助读者体会：

如下图所示，在一开始，我们考虑相距最远的两个柱子所能容纳水的面积。水的宽度是两根柱子之间的距离 d = 8；水的高度取决于两根柱子之间较短的那个，即左边柱子的高度 h = 3。水的面积就是 3 * 8 = 24。

如果选择固定一根柱子，另外一根柱子变化。水的面积会有如下变化：

• 当前柱子是最两侧的柱子，水的宽度 d为最大，其他的组合，水的宽度都比这个小。
• 左边柱子较短，决定了水的高度为3。如果移动左边的柱子，新的水面高度不确定，但一定不会超过右边的柱子高度 7。
• 如果移动右边的柱子，新的水面高度一定不会超过左边的柱子高度 3，也就是不会超过现在的水面高度，而水池宽度却在减小，容量不增反减。

由此可见，如果固定左边的柱子，移动右边的柱子，那么水的高度一定不会增加，且宽度一定减少，所以水的面积一定减少。较短的柱子(左边的柱子)和任意一个其他柱子的组合其实都可以进行排除。也就是我们可以排除掉左边的柱子了。

这个排除掉左边柱子的操作，就是双指针代码里的 i++。i 和 j 两个指针中间的区域都是还未排除掉的区域。随着不断的排除，i 和 j 都会往中间移动。当 i 和 j 相遇，算法就结束了。

详细代码如下：

class Solution {
public:
    int maxArea(vector& height) {
        // 先设立双指针
        int size = height.size();
        int i = 0, j =  size - 1;
        int res = 0;
        while (i < j) {
            int minHeight = height[i] < height[j] ? height[i++] : height[j--];
            int area = (j - i + 1) * minHeight;
            res = max(res, area);
        }
        return res;
    }
};

需要注意的是，代码进行了一定程度的简化。再比较得出minHeight时，已经对双指针其中之一的下标进行更改，所以计算当前水池深度时需要在下标差值的基础上加1。

167. 两数之和 II

题目描述

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

• 返回的下标值（index1 和 index2）不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

分析与题解

需要注意的是，有序数组已经是升序排列。初始状态我们选择首位和末位元素就行求和，并与目标值进行比较：

• 和大于目标值，更改末尾元素。此时如果进位首位元素，由于升序排列和只会更大，因此末尾元素与其他元素求和的组合均可舍弃。
• 和小于目标值，更改首位元素。此时如果缩进末尾元素，由于升序排列和只会更小，因此首位元素与其他元素求和的组合均可舍弃。
• 和等于目标值，直接返回即可。

代码如下：

class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        int size = numbers.size();
        int i = 0, j = size - 1;
        while ( i < j) {
            int sum = numbers[i] + numbers[j];
            // 因为数组是升序排列，将和与target比较
            // 1、sum < target 则抛弃较小的左边界
            // 2、sum > target 则抛弃较大的有边界
            if (sum == target) {
                return vector{i+1, j+1};
            }
            else if (sum < target) {
                i++;
            } else {
                j--;
            }
        }
        return vector{-1, -1};
    }
};

注意返回结果封装从vector形式，并且要求返回的下标值不是从0开始的。

240. 搜索二维矩阵 II

题目描述

编写一个高效的算法来搜索m x n矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10^9 <= target <= 10^9

分析与题解

仔细观察矩阵左下角或者右上角，对于左下角，往右走数字变大，往上走数字变小，
那么我们从左下角出发，target比当前值大，我们就往右走，target比当前值小，我们就往上走，若target存在一定会找到。

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        //注意判断空值
        int row  = matrix.size(), col = matrix[0].size();
        if (row == 0 || col == 0) return false;
        //初始化起点下标
        int i = row - 1, j = 0;
        while (i >= 0 && j < col) {
            if (matrix[i][j] < target) 
                j++;
            else if (matrix[i][j] > target)
                i--;
            else return true;
        }
        return false;
    }
};