class Solution {
public void moveZeroes(int[] nums) {
int left = 0,right = 0,len = nums.length;
for(int i = 0;i < len;i++){
if(nums[i] == 0){
left = i;//若为0 放置左指针
for(int j = left;j < len;j++){//开始移动右指针
if(nums[j] != 0){//找到不为0的右指针
right = j;
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;//交换左右指针
break;//结束
}
}
}
}
}
}class Solution {
public int maxArea(int[] height) {
int len = height.length;
int left = 0,right = len - 1;//初始化两个指针 一个在最左 一个在最右
int max = 0;//初始化max
while(left < right){//确定右指针只能在左指针右边 保证不会越界
if(height[left] > height[right]){//若左比右高 就按右边的算面积
max = Math.max((right - left) * height[right],max);
right--;
}else{//若右比左高 就按左边的算面积
max = Math.max((right - left) * height[left],max);
left++;
}
}
return max;
}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
/**
本题主要是去重
*/
int len = nums.length;
Arrays.sort(nums);//首先排序 默认从大到小
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0;i < len - 2;i++){//i 是第一个指针，用来表示第一个数的位置
if(nums[i] > 0) break;//去重：如果第一个数就大于0 剩下的数都会大于0 不可能得出结果
if(i != 0 && nums[i] == nums[i-1]) continue;//如果第一个数和上一个数重复 去重
int m = i + 1,n = len - 1;//确定两个指针的位置 即左指针为第一个数+1 右指针为最后一位
while(m < n){//开始收缩
int sum = nums[i] + nums[m] + nums[n];//用和来判断如何收缩
if(sum == 0){//找到了结果为0
list.add(Arrays.asList(nums[i],nums[m],nums[n]));//加入list作为答案
while(m < n && nums[m] == nums[m + 1]) m++;//如果左指针有相同的情况 就继续移动去重
while(m < n && nums[n] == nums[n - 1]) n--;//如果右指针有相同的情况 就继续移动去重
m++;//收缩左指针
n--;//收缩右指针
}else if(sum > 0){//如果和大于0 那么移动右指针 让右边值变小
n--;
}else if(sum < 0){//如果和小于0 那么移动左指针 让左边值变大
m++;
}
}
}
return list;
}
}class Solution {
public int trap(int[] height) {
/**
栈可以做 但是动态规划加双指针做非常简单
*/
/**
单动态规划版
int len = height.length;
int[] max_left = new int[len];
int[] max_right = new int[len];
int sum = 0;
for(int i = 1;i < len - 1;i++){
max_left[i] = Math.max(max_left[i - 1],height[i - 1]);//给每个区域的值算出左边最高的
}
for(int i = len - 2;i >= 0;i--){
max_right[i] = Math.max(max_right[i + 1],height[i + 1]);//给每个区域的值算出右边最高的
}
for(int i = 1;i < len - 1;i++){
int min = Math.min(max_left[i],max_right[i]);//比较每个区域左右边最高的值 取最小
if(min > height[i]){//若这个最小值大于当前值 证明是有蓄水空间的
sum += min - height[i];//加上sum
}
}
return sum;
*/
/**
栈版
class Solution {
public int trap(int[] height) {
int size = height.length;
if(size <= 2) return 0;
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
int sum = 0;
for(int index = 1;index < size;index++){
int stackTop = stack.peek();
if(height[index] < height[stackTop]){
stack.push(index);
}else if(height[index] == height[stackTop]){
stack.pop();
stack.push(index);
}else{
int heightAtIdx = height[index];
while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
int mid = stack.pop();
if (!stack.isEmpty()){
int left = stack.peek();
int h = Math.min(height[left], height[index]) - height[mid];
int w = index - left - 1;
int hold = h * w;
if (hold > 0) sum += hold;
stackTop = stack.peek();
}
}
stack.push(index);
}
}
return sum;
}
}
*/
//双指针加动态规划版
int n = height.length;
int res = 0;
// 左右指针：分别指向左右两边界的列
int left = 0, right = n - 1;
// 左指针的左边最大高度、右指针的右边最大高度
int leftMax = height[left], rightMax = height[right];
// 最两边的列存不了水
left++;
right--;
// 向中间靠拢
while(left <= right){
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if(leftMax < rightMax){
/**
这个循环有一点难看懂
但是注意一点：height[left] 和 height[right]表示的是当前处理的值
这是不断收缩的双指针，说明是在俩个方向收缩处理的
当leftMax < rightMax时 证明当前左边的值更小 要用左边值来计算
而为什么leftMax - height[left]呢？
因为leftMax是先前和height[left]比较过的 证明leftMax是一定大于等于height[left]的
所以可以不用比较直接结果相加
*/
res += leftMax - height[left];
left++;
}else{
// 右边同理
res += rightMax - height[right];
right--;
}
}
return res;
}
}双指针的题目也不算难，记住left < right的循环公式就好。之前看接雨水栈的写法太难了，有些神化了这道题，再看动态规划的发现实在太简单了。双指针可以再看Acwing巩固一下格式就行。
Comments NOTHING