Hot100 Java之Acm模式 4-7（双指针）
283. 移动零
题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
代码
import java.util.*;
public class hot100 {
public static void main(String[] args) {
/*移动零：要原地操作，不能复制数组，考虑双指针
* 快指针遍历数组，指向判断的元素，是0就后移，不是0，就把当前元素插入slow
* 慢指针指向待插入下标，如果快指针不是0，慢指针插入非0元素，然后后移*/
//时间复杂度o(n),只用遍历数组
//空间复杂度o(1),原地操作
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //数组长度
int[] nums = new int[n];
for(int i=0; i < nums.length; i++){
nums[i] = sc.nextInt();
}
int fast = 0;
int slow = 0;
//快指针遍历数组
while(fast < nums.length){
if(nums[fast] != 0){ //非0元素
nums[slow] = nums[fast]; //移动fast到slow
slow++; //slow后移，指向下一个待插入位置
}
fast++; //不管是不是0，快指针都要后移
}
//后续补0
while(slow < nums.length){
nums[slow] = 0;
slow++;
}
for(int i : nums){
System.out.print(i + " ");
}
}
}
11.盛最多水的容器
题目
给定一个长度为 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。
代码
import java.util.*;
public class hot100 {
public static void main(String[] args) {
/*盛水最多的容器：双指针+贪心思想
* 左指针从0开始，右指针从最后开始，不断向中间靠近
* 容器的面积=(右指针-左指针)*最小的高度
* 选哪个指针向中间靠近，取决于哪个更短，移动短的，更容易得到最大容量*/
//时间复杂度o(n),左右指针只用遍历数组
//空间复杂度o(n),存储数组
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for(int i=0; i < n; i++){
nums[i] = sc.nextInt();
}
int l = 0;
int r = nums.length - 1;
int res = 0;
while(l < r){
//!!!(r - l)作为底
int area = (r - l) * Math.min(nums[r], nums[l]); //计算面积
res = Math.max(res, area);
//移动指针,更短的移动
if(nums[l] < nums[r]){
l++;
}
else{
r--;
}
}
System.out.println(res);
}
}
15.三数之和
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
代码
import java.util.*;
public class hot100 {
public static void main(String[] args) {
/*三数之和，下标不同3个数和为0，找到所有的组合
* 一个i固定，j和k作为左右指针，向中间移动，不断寻找后面2个数字
* 如果sum=0，加入结果，j++，k--,都向中间移动
* 如果sum太大，k--，如果sum太小，j++
* 注意点在于如何去重，i去重，如果i不是第一个数，且i和i-1相等，那么这个i直接跳过，在i-1的时候，这个组合已经有了
* j去重，如果j不是第一个左指针，即j!=i+1,如果j和j-1相等，这个j也跳过，直接j++
* k去重，如果k不是最后一个右指针，即k!=nums.length-1,且k和k+1相等，这个k也跳过，直接k--*/
//时间复杂度o(n2),遍历i是o(n),双指针便利jk是o(n)
//空间复杂度o(n),存数组
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for(int i=0; i < n; i++){
nums[i] = sc.nextInt();
}
Arrays.sort(nums); //!!!要排序，才能用双指针
List<List<Integer>> res = new ArrayList<>();
for(int i=0; i < nums.length; i++){ //第一个数
//i去重
if(i != 0 && nums[i] == nums[i-1]){
continue;
}
int j = i + 1; //第二个数
int k = nums.length - 1; //第三个数
while(j < k){
//j去重,j-1包含了j的情况
if(j != i + 1 && nums[j] == nums[j-1]){
j++;
continue;
}
//k去重，k+1包含了k的情况
if(k != nums.length -1 && nums[k] == nums[k+1]){
k--;
continue;
}
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0){
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
k--;
}
else if(sum < 0){
j++;
}
else{
k--;
}
}
}
System.out.println(res);
}
}
42.接雨水
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
代码（双指针）
import java.util.*;
public class hot100 {
public static void main(String[] args) {
/*接雨水，双指针和单调栈都可以解，双指针代码更好写
* 单调栈，就是一个维护一个单调递减栈，出现高柱子再出栈，说明有凹槽可以统计容量
* 有雨水的地方，肯定是凹槽，容量取决于min(左边高度，右边高度）-本地高度
* 用一个left数组记录当前下标，左边最高的柱子，从左向右比较
* 用一个right数组记录当前下标，右边最高的柱子，从右向左比较*/
//时间复杂度o(n)
//空间复杂度o(n)
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for(int i=0; i < n; i++){
nums[i] = sc.nextInt();
}
int res = 0;
int[] left = new int[n];
int[] right = new int[n];
left[0] = nums[0];
for(int i=1; i < n; i++){
left[i] = Math.max(nums[i],left[i-1]); //左边最高的，当前高度和左边所有柱子里最高的
}
right[n-1] = nums[n-1];
for(int i=n-2; i >=0; i--){
right[i] = Math.max(nums[i], right[i+1]); //右边最高的，当前高度和右边所有柱子里最高的
}
for(int i=0; i < n; i++){ //统计面积
int area = Math.min(left[i], right[i]) - nums[i]; //凹槽面积，取决于左右高度的较小值-当前高度
res += area; //宽度都是1
}
System.out.println(res);
}
}
代码（单调栈，bug太多，不建议面试写）
import java.util.*;
public class hot100 {
public static void main(String[] args) {
/*接雨水，维护单调递减栈，出现递增说明凹槽出来了，栈内要放下标，因为凹槽的底长要知道
* 第一个元素直接入栈，后续元素如下
* 如果小于等于栈顶，还是向下的趋势，没有凹槽，高度入栈就行
* 如果高度大于栈顶，说明出现凹槽了，栈顶出栈作为凹槽的底，出栈后的栈顶是左高度，右高度是当前元素
* min(左高度-右高度）-凹槽高度=高，i-left-1=宽
* 例子 4 2 0 3 2 5 输出9就对了*/
//时间复杂度o(n),单调栈遍历
//空间复杂度o(n)
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for(int i=0; i < n; i++){
nums[i] = sc.nextInt();
}
int res = 0;
Stack<Integer> stack = new Stack<>(); //单调递减栈
for(int i=0; i < n; i++){
//栈空，或者元素值更小，直接入栈
if(stack.isEmpty() || nums[i] <= nums[stack.peek()]){ //!!!nums[stack.peek()],是下标
stack.push(i); //下标入栈
}
//说明nums[i]比栈顶高了，有凹槽了
else{
//!!!while,只要nums[i]更大，栈内元素都要出栈，都是凹槽
while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){ //!!!nums[stack.peek()],是下标
int mid = stack.pop(); //凹槽点
//!!!if,要有if判断栈非空，如果mid在最左边，下面peek会报错，保证peek成功
if(!stack.isEmpty()){
int left = stack.peek(); //左边柱子
//!!!i-left-1，i-mid是错的
int area = (Math.min(nums[left], nums[i]) - nums[mid]) * (i - left - 1);
res += area;
}
}
//！！！不要忘记当前元素下标，处理完栈内的更小元素
stack.push(i);
}
}
System.out.println(res);
}
}