283. 移動零

leetcode鏈接：https://leetcode.cn/problems/move-zeroes/

給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。請注意 ，必須在不復(fù)制數(shù)組的情況下原地對數(shù)組進(jìn)行操作。示例 1:輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]
示例 2:輸入: nums = [0]
輸出: [0]
提示:1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
進(jìn)階：你能盡量減少完成的操作次數(shù)嗎？

這題就是一個典型的快慢指針問題，類似于從數(shù)組中刪除指定元素?？熘羔樢来伪闅v，慢指針用來存放元素。思路就是先把所有的0元素刪除，再在數(shù)組末位填充0，代碼如下：

class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;for(int  i = 0 ; i < nums.size(); i++){if(nums[i] != 0){nums[slow++] =nums[i];}}//把剩下的位置填充為0for(int i = slow; i < nums.size(); i++){nums[i] = 0;}}
};

11.盛最多水的容器

給定一個長度為 n 的整數(shù)數(shù)組 height 。
有 n 條垂線，第 i 條線的兩個端點(diǎn)是 (i, 0) 和 (i, height[i]) 。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。返回容器可以儲存的最大水量。說明：你不能傾斜容器。

這題是貪心算法，

42. 接雨水

給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。示例 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 個單位的雨水（藍(lán)色部分表示雨水）。 
示例 2：輸入：height = [4,2,0,3,2,5]
輸出：9

對于這種問題，我們不要想整體，而應(yīng)該去想局部。僅僅對于位置 i，能裝下多少水呢？

能裝 2 格水，因為 height[i] 的高度為 0，而這里最多能盛 2 格水，2-0=2。

為什么位置 i 最多能盛 2 格水呢？因為，位置 i 能達(dá)到的水柱高度和其左邊的最高柱子、右邊的最高柱子有關(guān)，我們分別稱這兩個柱子高度為 l_max 和 r_max；位置 i 最大的水柱高度就是 min(l_max, r_max)。

也就是說：

water[i] = min(# 左邊最高的柱子max(height[0..i]),  # 右邊最高的柱子max(height[i..end]) ) - height[i]

根據(jù)該思路寫一個暴力解法。

暴力解法

class Solution {
public:int trap(vector<int>& height) {int res = 0;for(int i = 1; i < height.size() - 1; i++){//這樣才能保證左右都有柱子int leftMax= 0, rightMax = 0;for (int j = i; j < height.size(); j++)rightMax = max(rightMax, height[j]);// 找左邊最高的柱子for (int j = i; j >= 0; j--)leftMax = max(leftMax, height[j]);cout<< leftMax << ',' << rightMax << endl;res += max(0, min(leftMax,rightMax) - height[i]);}return res;}
};

時間復(fù)雜度O（n2），實際上不需要每次都遍歷，可以借助備忘錄。

這里實際上res加的時候時候不需要和0比較，因為在計算 l_max 數(shù)組的時候是取「自己高度」和「目前左邊最高」的最大值，因此 l_max[i] >= height[i] 是恒成立的。r_max 同理。

備忘錄

不用每次都計算left和right，計算一次就好，存儲在兩個數(shù)組中：

class Solution {
public:int trap(vector<int>& height) {if (height.size() == 0) {return 0;}int res = 0;vector<int> leftMax(height.size(), 0);vector<int> rightMax(height.size(), 0);leftMax[0] = height[0];rightMax[height.size() - 1] = height[height.size() - 1];for(int i = 1; i < height.size() - 1; i++){//這樣才能保證左右都有柱子leftMax[i] = max(height[i], leftMax[i - 1]);}for(int i = height.size() - 2; i >= 0; i--){rightMax[i] = max(height[i], rightMax[i + 1]);}for(int i = 1; i < height.size() - 1; i++){res += min(leftMax[i],rightMax[i]) - height[i];}return res;}
};

把時間復(fù)雜度降低為 O(N)，已經(jīng)是最優(yōu)了，但是空間復(fù)雜度是 O(N)。雙指針法可以把空間復(fù)雜度降到O(1)。

雙指針法

之前不管是暴力解法還是備忘錄，leftMax和rightMax分別代表 height[0..i] 和 height[i..end] 的最高柱子高度：

而在雙指針法中，代表的是 height[0..left] 和 height[right..end] 的最高柱子高度：

我們只在乎 min(l_max, r_max)。對于上圖的情況，我們已經(jīng)知道 l_max < r_max 了，至于這個 r_max 是不是右邊最大的，不重要。重要的是 height[i] 能夠裝的水只和較低的 l_max 之差有關(guān)。

最終代碼：

class Solution {
public:int trap(vector<int>& height) {int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;int res = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);// res += min(leftMax, rightMax) - height[i]if (leftMax < rightMax) {res += leftMax - height[left];left++;} else {res += rightMax - height[right];right--;}}return res;}
};

11. 盛最多水的容器

給定一個長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，
第 i 條線的兩個端點(diǎn)是 (i, 0) 和 (i, height[i]) 。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。返回容器可以儲存的最大水量。說明：你不能傾斜容器。

輸入：[1,8,6,2,5,4,8,3,7] 輸出：49 解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。

跟上面的題類似，直接貼代碼：

class Solution {
public:int maxArea(vector<int>& height) {int res = 0;int left = 0, right = height.size() - 1;while(left < right){res = max(res, min(height[left], height[right]) * (right - left));if(height[left] < height[right]){left++;}else{right--;}}return res;}
};

這里要注意雙指針的移動順序，為什么是往height[i]小的那邊移動？因為矩形的最大面積是由最短的那條邊決定的：如果移動較低的那一邊，那條邊可能會變高，使得矩形的高度變大，進(jìn)而就「有可能」使得矩形的面積變大；相反，如果你去移動較高的那一邊，矩形的高度是無論如何都不會變大的，所以不可能使矩形的面積變得更大。

總結(jié)

感覺這樣復(fù)習(xí)還是太零散沒有體系了，從明天開始，還是按照模塊來，先把原來的題二刷掉，然后再找拓展題。