LeetCode Hot 100 第二天
1. 283 移动零
链接：题目链接
题解：
要求：时间复杂度 < O (n^2)
题解：将非零元素依次往前移（占据0元素的位置），最后再将0元素填充至数组尾。时间复杂度O(n)，用一个指针x来维护非零元素的起始位置，在用一个指针y从左到右遍历元素（跳过0元素），将y指针下标元素填充至x指针下标，x指针与y指针均往后移，填充完非零元素后，x指针往后移动，填充0元素。
代码：
public void moveZeroes(int[] nums) {if (nums.length == 1) {return;}int len = nums.length;int zeroLeftIndex = 0;for (int i = 0; i < len; ++i) {if (nums[i] != 0) {nums[zeroLeftIndex] = nums[i];zeroLeftIndex++;}}for (int i = zeroLeftIndex; i < len; ++i) {nums[i] = 0;}}
2. 11 盛最多水的容器
链接：题目链接
题解：
要求：时间复杂度 <= O(n logn)
题解：容纳水公式：(r - l) * Math.min(height[l], height[r])，假设答案区间为[l, r]，则要排除掉[l, r]子区间容水量，因为(r - l)子区间只会变得更小，所以仅当子区间Math.min(height[l], height[r])变大才有可能扩大容水量，才有可能容纳更多的水，那么我们需要把这类情况依次排除掉，所以这里要用到双指针，分别在区间左右两端，往内收让Math.min(height[l], height[r])变大（当height[r] > height[l]时，移动r指针是没用的，必须移动l指针），维护一个maxValue(最大容水量)。[l, r]父区间一样的考虑方法，所以需要把[l, r]扩至最大区间[0, height.length -1]。时间复杂度O(n)
代码：
public int maxArea(int[] height) {int len = height.length - 1;int l = 0, r = len;int maxValue = (r - l) * Math.min(height[l], height[r]);while(l < r) {if (height[l] < height[r]) {l ++;} else {r --;}maxValue = Math.max((r - l) * Math.min(height[l], height[r]), maxValue);}return maxValue;}
3. 15 三数之和
链接：题目链接
题解：
要求：时间复杂度 <= O(n^2)
题解：这里可以枚举前两个数字（需要先排序，保证不重复枚举），第三个数字可以通过 num = - (num[i] + num[j])计算得到，通过hash能O(1)时间复杂度判断是否存在该值。还需要注意去重，这里用Set去重。时间复杂度O(n^2)。
代码：
public List<List<Integer>> threeSum(int[] nums) {// 先对数组进行排序// 左右指针 枚举 前两个数字 相同数字最多出现一次(先右指针往右移 再枚举左指针往右移)// hashMap存储每个数组 对应出现的次数Set<List<Integer>> result = new HashSet<>();Arrays.sort(nums);Map<Integer, Integer> numCountMap = new HashMap<>();for (int num: nums) {numCountMap.put(num, numCountMap.getOrDefault(num, 0) + 1);}int len = nums.length;for (int i = 0; i < len; ) {for (int j = i + 1; j < len; ) {int target = -1 * (nums[i] + nums[j]);int repeatTargetCount = 0;if (nums[i] == target) {repeatTargetCount++;}if (nums[j] == target) {repeatTargetCount++;}Integer targetCount = numCountMap.getOrDefault(target, 0);if (targetCount > repeatTargetCount) {List<Integer> threeSum = Arrays.asList(nums[i], nums[j], target);Collections.sort(threeSum);result.add(threeSum);}do {j++;} while (j < len && nums[i] == nums[j]);}do {i++;} while (i < len && nums[i - 1] == nums[i]);}return new ArrayList<>(result);}4. 42 接雨水
链接：题目链接
题解：
要求：时间复杂度 <= O(nlogn)
题解：考虑第i列能接到多少水，只需要考虑 i列 左边最大高度 maxL 右边最大高度 maxR 取 Max(0, min(maxL, maxR) - nums[i])。左边指针往右走 边走边维护maxL。maxR 怎么维护? 右指针往左走 维护单调栈，单调栈 如果左边的高度 小于 单调栈内的高度 就不入栈 栈元素(下标, 高度)。遍历左指针时 如果下标 小于 指针下标 就出栈。时间复杂度O(n)
代码：
public int trap(int[] height) {// 考虑第i列 只需要考虑 i列 左边最大高度 maxL 右边最大高度 maxR 取 Max(0, min(maxL, maxR) - nums[i])// 左边指针往右走 边走边维护maxL// maxR 怎么维护? 右指针往左走 维护单调栈// 单调栈 如果左边的高度 小于 单调栈内的高度 就不入栈 栈元素(下标, 高度)// 遍历左指针时 如果下标 小于 指针下标 就出栈int len = height.length - 1;if (len == 0) {return 0;}Stack<Integer> stack = new Stack<>();for (int r = len; r >= 0; -- r) {if (stack.isEmpty()) {stack.push(r);} else if (height[stack.peek()] < height[r]) {stack.push(r);}}int maxL = height[0];int ans = 0;for (int i = 1; i < len; ++ i) {while (stack.peek() <= i) {stack.pop();} ans += Math.max(0, Math.min(maxL, height[stack.peek()]) - height[i]);maxL = Math.max(maxL, height[i]);}return ans;}如果对你有帮助，辛苦点个赞，谢谢啦，朋友！！！