盛最多水的容器
点击查看代码
class Solution {public int maxArea(int[] height) {int n = height.length;int l = 0;int r = n - 1;int res = Integer.MIN_VALUE;while(l < r){int s = (r - l) * Math.min(height[l],height[r]);res = Math.max(res, s);if(height[l] < height[r]){l++;}else{r--;}}return res;}
}
移动0
点击查看代码
class Solution {public void moveZeroes(int[] nums) {int i = 0;int j = 0;while(i < nums.length){if(nums[i] != 0){nums[j] = nums[i];j++;}i++;}while(j < nums.length){nums[j] = 0;j++;}}
}
接雨水
思路一：一个数组存前缀最大值，一个数组存后缀最大值，遍历原数组求和。
点击查看代码
class Solution {public int trap(int[] height) {int n = height.length;int[] pre_max = new int[n];int[] suf_max = new int[n];int pre = Integer.MIN_VALUE;int suf = Integer.MIN_VALUE;int res = 0;for(int i = 0; i < n ; i ++){pre = Math.max(pre,height[i]);pre_max[i] = pre; }for(int j = n-1; j >= 0 ; j--){suf = Math.max(suf,height[j]);suf_max[j] = suf; }for(int k = 0; k < n; k++){int sum = (Math.min(pre_max[k],suf_max[k]) - height[k]);res += sum;}return res;}
}
思路二：双指针，左指针代表前缀最大值，右指针代表后缀最大值；利用左指针遍历；前缀小于后缀，加前缀，反之加后缀。
点击查看代码
class Solution {public int trap(int[] height) {int pre_max = 0;int suf_max = 0;int l = 0;int r = height.length - 1;int res = 0;while(l <= r){suf_max = Math.max(suf_max, height[r]);pre_max = Math.max(pre_max, height[l]);if(pre_max < suf_max){int sum = pre_max - height[l];res += sum;l++;}else{int sum = suf_max - height[r];res += sum;r--;}}return res;}
}