例题一：11. 盛水最多的容器

思路

我们来换个角度来思考这个问题，上述的解法是通过两两组合，这无疑是完备的。我们换个角度思考，是否可以先计算长度为 n 的面积，然后计算长度为 n-1 的面积，… 计算长度为 1 的面积。 这样去不断更新最大值呢？很显然这种解法也是完备的，但是似乎时间复杂度还是 $O(n ^ 2)$, 不要着急。

考虑一下，如果我们计算 n-1 长度的面积的时候,是可以直接排除一半的结果的。比如我们计算 n 面积的时候，假如左侧的线段高度比右侧的高度低，那么我们通过左移右指针来将长度缩短为 n-1 的做法是没有意义的，因为新的形成的面积变成了(n-1) * heightOfLeft 这个面积一定比刚才的长度为 n 的面积 （n * heightOfLeft） 小。也就是说最大面积一定是当前的面积或者通过移动短的端点得到。

代码

class Solution {public int maxArea(int[] height) {int max = 0, i = 0, j = height.length - 1;while(i < j){max = Math.max(max, Math.min(height[i], height[j])*(j-i));if(height[i] < height[j])i++;elsej--;}return max;}
}

复杂度

• 时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 $O(N)$。
• 空间复杂度：$O(1)$。

例题二：875. 爱吃香蕉的珂珂

思路

采用二分法，由题可知，$1<=K<=1,000,000,000$，此题为寻找最小的满足要求的数。在计算吃香蕉的总时间时，有一个小技巧：$time += (piles[i] - 1) / K + 1$。

代码

class Solution {public int minEatingSpeed(int[] piles, int H) {int low = 1;int high = 1_000_000_000;while(low < high){int middle = (high + low) / 2;if(possible(piles, H, middle)){high = middle;}else{low = middle + 1;}}return low;}public boolean possible(int[] piles, int H, int K){int time = 0;for(int each : piles)time += (each - 1) / K + 1;return time <= H;}
}

复杂度

• 时间复杂度$O(Nlog(W))$
• 空间复杂度$O(1)$

N为香蕉的堆数， W为最大堆的橡胶数

例题三：26. 删除排序数组中的重复项

思路

快慢指针

代码

class Solution {public int removeDuplicates(int[] nums) {if(nums.length == 0) return 0;int i = 0, j = 1;while(j < nums.length){if(nums[j] == nums[i])j++;elsenums[++i] = nums[j++];}return i+1;}
}

复杂度

• 时间复杂度$O(N)$
• 空间复杂度$O(1)$

N为数组的长度

例题四：167. 两数之和 II - 输入有序数组

思路

如果是无序的，可以用哈希表。如果是有序，也可以用双指针，从两边向中间靠拢。

代码

class Solution {public int[] twoSum(int[] numbers, int target) {int i = 0, j = numbers.length-1;while(i < j){int sum = numbers[i] + numbers[j];if(sum > target)j--;else if(sum < target)i++;elsereturn new int[]{i+1, j+1};}return new int[]{0,0};}
}

复杂度

• 时间复杂度$O(N)$
• 空间复杂度$O(1)$

N为数组长度

例题五：42. 接雨水

方法一：暴力解法

思路

针对数组中的每一个元素，求它所能接住的雨水量，具体方法是分别求它左右两边的最大高度（将它自己也考虑进去），其中的较小值与当前的高度的差值就是它所能接住的雨水量。

代码

class Solution {public int trap(int[] height) {int sum = 0;for(int i = 0; i < height.length; i++){int maxLeft = height[i], maxRight = height[i];for(int j = i; j >=0; j--){if(height[j]>maxLeft)maxLeft = height[j];}for(int j = i; j <height.length; j++){if(height[j]>maxRight)maxRight = height[j];}sum += Math.min(maxLeft, maxRight) - height[i];}return sum;}
}

复杂度

• 时间复杂度$O(N^2)$
• 空间复杂度$O(1)$

方法二：动态编程

思路

暴力解法中，针对每一个位置，都要求它左边的最大高度和右边的最大高度。实际上，我们可以事先将这些数据都计算并储存起来，需要用的时候就可以直接用了，这种方法叫做动态编程。具体做法是维护两个数组。

代码

class Solution {public int trap(int[] height) {if(height.length == 0) return 0;int sum = 0;int[] leftMax = new int[height.length];int[] rightMax = new int[height.length];leftMax[0] = height[0];for(int i = 1; i < height.length; i++){leftMax[i] = Math.max(height[i], leftMax[i-1]);}rightMax[height.length-1] = height[height.length-1];for(int i = height.length-2; i > -1; i--){rightMax[i] = Math.max(height[i], rightMax[i+1]);}for(int i = 0; i < height.length; i++){sum += Math.min(leftMax[i], rightMax[i]) - height[i];}return sum;}
}

复杂度

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

方法三：双指针

思路

由图可知，在最高的bar的左面，每个位置积水的数量取决于leftMax，在最高的bar的右面，则取决于rightMax。所以，

代码

class Solution {public int trap(int[] height) {int left = 0, right = height.length - 1;int leftMax = 0, rightMax = 0; int sum = 0;while(left <= right){if(height[left] < height[right]){if(leftMax < height[left]){leftMax = height[left];}else{sum += leftMax - height[left];}left++;}else{if(rightMax < height[right]){rightMax = height[right];}else{sum += rightMax - height[right];}right--;}}return sum;}
}

复杂度

• 时间复杂度$O(N)$
• 空间复杂度$O()$

例题六：面试题 17.11. 单词距离

方法一：双指针

思路

用双指针，在遍历数组的过程中更新最小差值。一定要注意，字符串的比较要用equals！不能用==！

代码

class Solution {public int findClosest(String[] words, String word1, String word2) {int res= words.length;int w1 = -1, w2 = -1;for(int i = 0; i < words.length; i++){if(words[i].equals(word1)){w1 = i;if(w1 != -1 && w2 != -1)res = Math.min(res, Math.abs(w1-w2));}else if(words[i].equals(word2)){w2 = i;if(w1 != -1 && w2 != -1)res = Math.min(res, Math.abs(w1-w2));}}return res;}
}

复杂度

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

方法二：哈希表

思路：

因为这个过程要重复多次，所以很容易想到用哈希表来存储单词极其对应的下标，于是这道题转换成从两组有序的数组中找到最小的差值。

代码

class Solution {public int findClosest(String[] words, String word1, String word2) {Map<String, List<Integer>> map = new HashMap<>();for(int i = 0; i < words.length; i++){if(!map.containsKey(words[i]))map.put(words[i], new ArrayList<Integer>());map.get(words[i]).add(i);}List<Integer> list1 = map.get(word1);List<Integer> list2 = map.get(word2);if(list1 == null || list2 == null)return 0;int i = 0, j = 0, res = Integer.MAX_VALUE;while(i < list1.size() && j < list2.size()){if(list1.get(i) < list2.get(j)){res = Math.min(res, list2.get(j)-list1.get(i));i++;}else{res = Math.min(res, list1.get(i)-list2.get(j));j++;}}return res;}
}

复杂度

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$