283. 移动零
题目描述
代码实现
分析：
快慢指针，快指针指向不为0的数，慢指针指向左边当前已经处理好的序列的尾部
代码：
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
int n = nums.length;
while(fast < n){
if(nums[fast] != 0){
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
fast++;
}
}
}
11. 盛最多水的容器
题目描述
代码实现
分析：
-
暴力做法，两个for循环，依次遍历每两个柱子之间的面积，注意这里题目说的意思是选定了两个柱子，其它柱子就没有。
点击查看代码，暴力会超时！
class Solution { public int maxArea(int[] height) { int area = 0; for (int i = 0; i < height.length; i++) { for (int j = i + 1; j < height.length; j++){ int areat= Math.min(height[i], height[j]) * (j-i); area = Math.max(area, areat); } } return area; } } -
双指针：有点像贪心，left 和 right 一定是选最小的那个值作为高度，假设宽度为t （下标之差）， 那么假设left是最小的，它的面积就是height[left] * t, 再往后，就算right左边还有更高的，面积也是不可能大于height[left] * t的。因为，首先，t就变小了，t-1或者更小。 其次，如果right左边有更低的，比left还低，那面积肯定就更小了。所以这个left就可以舍去了，或者说，最小值的那条边的
剩余情况就可以舍去了，不用再考虑了。
代码：
class Solution {
public int maxArea(int[] height) {
int area = 0;
int left = 0;
int right = height.length - 1;
while (left < right){
int min = Math.min(height[left], height[right]);
int areaTemp = min * (right - left);
area = Math.max(area, areaTemp);
if(min == height[left]) {
left++;
}else {
right--;
}
}
return area;
}
}
15. 三数之和
题目描述
代码实现
分析：
注意去重
代码：
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++){
// 对第一个元素去重
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[left] + nums[right];
if (sum < 0 - nums[i]){
left++;
}else if(sum > 0 - nums[i]){
right--;
}else { // 相等，找到一组
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
// 对第二个元素去重
while(left < right && nums[left] == nums[left + 1]) left++;
// 对第三个元素去重
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
}
42. 接雨水
题目描述
代码实现
分析：
最关键是要找到对于每个柱子来说，它左边的 最大值 和右边的 最大值，两者取最小值，再减去柱子的值，就是它自己可以接的水。纯暴力的话就是要对每个柱子都计算出来
-
单调栈解法 横着计算 单调栈详解
点击查看代码
class Solution { public int trap(int[] height) { Deque<Integer> stack = new LinkedList<>(); int res = 0; // 单调栈 // 从左到右， 遇到高的柱子，就可以计算含水量了 stack.push(0); for(int i = 1; i < height.length; i++){ if(height[i] < height[stack.peek()]){ stack.push(i); }else if(height[i] == height[stack.peek()]){ stack.pop(); stack.push(i); }else { // height[stack.peek()] < height[i] while(!stack.isEmpty() && height[stack.peek()] < height[i]){ int mid = stack.pop(); if(!stack.isEmpty()){ int left = stack.peek(); int right = i; int cnt = Math.min(height[left], height[right]) - height[mid]; System.out.println(cnt * (right - left -1)); res += cnt * (right - left -1); } } stack.push(i); } } return res; } } -
前后缀分解 竖着计算
点击查看代码
class Solution { public int trap(int[] height) { int[] pre = new int[height.length]; int[] suf = new int[height.length]; int ans = 0; pre[0] = height[0]; for(int i = 1; i < height.length; i++){ pre[i] = Math.max(pre[i-1], height[i]); System.out.print(pre[i]); } suf[height.length -1] = height[height.length-1]; for(int i = height.length -2; i >= 0; i--){ suf[i] = Math.max(suf[i+1], height[i]); } for(int i = 0; i < height.length; i++){ ans += Math.min(suf[i], pre[i]) - height[i]; } return ans; } } -
双指针 竖着计算
这里说的前缀后缀可以想象成木板的长度。
preMax 记录着到达 left 的最大前缀，sufMax 记录着到达 right 的最大后缀，找到当前，preMax 和 sufMax 的最小值。
比如，当 preMax 比 sufMax 小的时候，对于 left 来说，它的后缀一定是大于等于这个时候的 sufMax 的，而它的前缀最大也知道了，就是当前的 preMax。
同理，对于right来说，当 sufmax<preMax 的时候，说明它的前缀一定是大于等于这个时候的 preMax，而它的后缀最大也知道了，就是当前的 sufMax，自然可以计算。
sufmax 和 preMax 相等的时候就无所谓哪个加了。
代码：
class Solution {
public int trap(int[] height) {
int n = height.length;
int left =0;
int right = n-1;
int preMax = 0;
int sufMax = 0;
int ans = 0;
while(left < right){
preMax = Math.max(preMax, height[left]);
sufMax = Math.max(sufMax, height[right]);
// 找到小的那边，小的那边说明已经确定可以装多少水了
if (preMax < sufMax){
ans += preMax - height[left];
left++;
}else {
ans += sufMax - height[right];
right--;
}
}
return ans;
}
}