目錄

缺失的第一個(gè)正數(shù)

接雨水

0ms，100% 代碼

---

缺失的第一個(gè)正數(shù)

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/first-missing-positive

題目：給你一個(gè)未排序的整數(shù)數(shù)組 nums ，請(qǐng)你找出其中沒有出現(xiàn)的最小的正整數(shù)。
請(qǐng)你實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 并且只使用常數(shù)級(jí)別額外空間的解決方案。

示例 1：

輸入：nums = [1,2,0]
輸出：3

示例 2：

輸入：nums = [3,4,-1,1]
輸出：2

示例 3：

輸入：nums = [7,8,9,11,12]
輸出：1

提示：

??? 1 <= nums.length <= 5 * 105
??? -231 <= nums[i] <= 231 - 1

思路：

（1）映射一個(gè)關(guān)系為數(shù)組 a[i] 存的值為 i+1，所以當(dāng) a[i] = x時(shí)，x的下標(biāo)就位 x-1

（2）0 -> a.length 循環(huán)，將 a[i] 放到 a[i] - 1 位置，如果a[a[i] - 1] != a[i] 就將兩個(gè)數(shù)位置調(diào)整

（3）循環(huán)判斷缺失了的數(shù)，如果a[i] != i + 1，缺失的數(shù)就是 i+1，循環(huán)完后還沒有找到那就是返回a.length+1

class Solution {public int firstMissingPositive(int[] nums) {for (int i = 0; i < nums.length; i++) {while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {//當(dāng) nums[i]大于零 且 nums[i]小于nums的長度 且 nums[nums[i - 1]]不等于nums[i] 的時(shí)候循環(huán)//nums[nums[i - 1]]和nums[i]進(jìn)行交換int temp = nums[nums[i] - 1];nums[nums[i] - 1] = nums[i];nums[i] = temp;}}//判斷缺失的數(shù)for (int i = 0; i < nums.length; i++) {if (nums[i] != i + 1) return i + 1;}return nums.length + 1;}
}

---

接雨水

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/trapping-rain-water
?

題目：給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6

解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）。

?

示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

提示：

??? n == height.length
??? 1 <= n <= 2 * 104
??? 0 <= height[i] <= 105

思路：

（1）需要先找到第一個(gè)大于0的柱子當(dāng)做U型的左邊

（2）左邊固定下來后去找右邊的柱子，右邊的柱子有兩種可能性

1）右邊找到的第一個(gè)柱子>=左邊的柱子

2）右邊找到的第一個(gè)柱子<左邊的柱子，但不能為0

（3）求出左邊柱子與右邊柱子中間的空隙，這里我使用了窮舉的方法嘗試所有的可能性

class Solution {public int trap(int[] height) {int ans = 0;//存放接水的數(shù)量int left = 0;//存放左邊柱子的高度，默認(rèn)為0for(int i = 0; i < height.length; i++) {if(height[i] >= 1) {//左側(cè)的柱子必須大于等于一才可以接水left = i++;//左側(cè)柱子高度等于iint now = 0;while(i < height.length && height[i] < height[left]) {//右邊小于左邊才可以存儲(chǔ)now += height[left] - height[i++];//左邊減去右邊}if(i < height.length) {ans += now;i--;//for后會(huì)有i++，所以要--來抵消++，右邊的柱子可以當(dāng)做下一個(gè)U型的左側(cè)柱子} else {//右邊柱子都比左邊的低i = left - 1;//回到左邊的左邊，i++抵消，重新回到leftheight[left]--;//每次減去1去匹配右邊更低的柱子}}}return ans;}
}

0ms，100% 代碼

class Solution {public int trap(int[] height) {int left = 0, right = height.length - 1;int maxL = height[left], maxR = height[right];int res = 0;while (left < right) {maxL = Math.max(maxL, height[left]);maxR = Math.max(maxR, height[right]);res += maxR > maxL ? maxL - height[left++] : maxR - height[right--];}return res;}
}

?

?