移动零

题目链接
题目描述：

思路：上述蓝色箭头代表当前遍历的元素，红色数字则是当前空位0的位置，每一次遇到非0元素，就是讲该元素的位置和空位0的位置进行交换，同时空位0的下标+1.

代码

class Solution {public void moveZeroes(int[] nums) {int zeroIndex = 0 ;for(int i = 0 ; i < nums.length ; i++){if(nums[i] != 0){int tmp = nums[i];nums[i] = nums[zeroIndex];nums[zeroIndex] = tmp;zeroIndex++;}}}
}

---

盛水最多的容器

题目链接
题目描述：

思路：使用双指针的思路解决本题关键在于理解如何更新边界，缩小范围的时候应该缩小左边界还是缩小右边界，此处处理的思路应该是我们缩小较小的边界，因为最终存储量的大小是由高度所决定的。

代码

class Solution {public int maxArea(int[] height) {int res = 0;int left = 0;int right = height.length - 1;while (left < right) {int h = Math.min(height[left], height[right]);int w = right - left;res = Math.max(h * w, res);if (height[left] < height[right]) {left++;} else {right--;}}return res;}
}

---

三数之和

题目链接
题目描述：

思路: 遍历nums,当前下标为i的元素,与它的和为0的两个元素只可能在这个元素之后,因此,对这个元素之后的元素采用双指针来便利.(注意跳过重复的情况).

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);for(int i = 0 ; i < nums.length ; i++){// 原始数据已经按照从大到小进行排序了,当当前下标的元素大于0,就没有必要继续检测了if(nums[i] > 0) return res;// 如果相邻的元素的值相同,那么他们查找出来的结果一定是重复的,所以要跳过.if(i > 0 && nums[i - 1] == nums[i])continue;int right = nums.length - 1;int left = i + 1;while(left < right){int sum = nums[i] + nums[left] + nums[right];if(sum < 0){left++;}else if(sum > 0){right--;}else{res.add(Arrays.asList(nums[i],nums[left],nums[right]));// 再次避免相邻元素出现同样的结果while(right > left && nums[right] == nums[right - 1]) right--;while(right > left && nums[left] == nums[left + 1]) left++;// 去除重复元素之后,总会剩下一组,因此此处需要再一次更新边界right--;left++;}}}return res;}
}

---

接雨水

题目链接
题目描述：

代码

双指针

力扣官方图片:

class Solution {public int trap(int[] height) {int len  = height.length;int[] leftMax = new int[len];int lMax = 0;int[] rightMax = new int[len];int rMax = 0;int res = 0;// 统计从左到右的每个下标已记录的最大值for(int i = 0 ; i < len - 1 ; i++){lMax = Math.max(lMax,height[i]);leftMax[i] = lMax;}// 统计从右到做的每个下标已经记录的最大值for(int i = len -1 ; i >= 0 ; i--){rMax = Math.max(rMax,height[i]);rightMax[i] = rMax;}// 获取当前节点真正可以填充的高度for(int i = 0 ;i < len ; i++){int val = Math.min(leftMax[i],rightMax[i]) - height[i];if(val > 0)res += val;}return res;}
}

单调栈(待补充)

class Solution {public int trap(int[] height) {int res = 0;Deque<Integer> stack = new LinkedList<>();int len = height.length;stack.push(0);for (int right = 1; right < len; right++) {if (height[stack.peek()] >= height[right]) {stack.push(right);} else {while (!stack.isEmpty() && height[stack.peek()] < height[right]) {int bottom = stack.pop(); // 底部索引（原left）if (stack.isEmpty()) break;int leftIndex = stack.peek(); // 左边界索引（原mid）// 计算雨水高度：min(左边界高, 右边界高) - 底部高int h = Math.min(height[leftIndex], height[right]) - height[bottom];// 计算雨水宽度：右边界 - 左边界 - 1int w = right - leftIndex - 1;res += h * w; // 雨水量 = 高度 × 宽度}stack.push(right); // 当前索引入栈}}return res;}
}

---