給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
請注意 ，必須在不復制數組的情況下原地對數組進行操作。

輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]

解法1：雙指針+交換
指針L：維護一個非零序列，L之前的元素都是非零的元素
指針R：尋找非零的元素，將其加入到L維護的序列中

public void moveZeroes(int[] nums) {int l = 0;int r = 0;while(r<nums.length){if(nums[r]!=0)swap(nums,l++,r);r++;}
}public void swap(int[] nums,int l,int r){if(l == r) return;nums[l] = nums[l] ^ nums[r];nums[r] = nums[l] ^ nums[r];nums[l] = nums[l] ^ nums[r];
}

func moveZeroes(nums []int)  {slow := 0for i,_ := range nums{if nums[i]!=0{tmp := nums[slow]nums[slow] = nums[i]nums[i] = tmpslow++}}
}

解法2：雙指針+賦值0
解法和1類似，只不過1是交換非零元素和0元素，2將非零元素全部移動到前面，后面統一賦值為0

public void moveZeroes(int[] nums) {int cur = 0;for(int i=0; i<nums.length; i++){if(nums[i]!=0){nums[cur++] = nums[i];}}for(;cur<nums.length; cur++){nums[cur] = 0;}
}

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

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

解放1：雙指針

在每個狀態下，無論長板或短板向中間收窄一格，都會導致水槽 底邊寬度 ?1-1?1 變短：

• 若向內 移動短板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能變大，因此下個水槽的面積 可能增大 。
• 若向內 移動長板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 不變或變小，因此下個水槽的面積 一定變小 。

因此，初始化雙指針分列水槽左右兩端，循環每輪將短板向內移動一格，并更新面積最大值，直到兩指針相遇時跳出；即可獲得最大面積。

public int maxArea(int[] height) {int l = 0;int r = height.length-1;int area = 0;while(l<r){if(height[l]<height[r]){int cur = height[l]*(r-l);area = Math.max(area, cur);l++;}else{int cur = height[r]*(r-l);area = Math.max(area, cur);r--;}}return area;
}

func maxArea(height []int) int {l,r := 0,len(height)-1res := 0for l<r {if height[l] < height[r]{res = int(math.Max(float64(res),float64(height[l]*(r-l))))l++;}else{res = int(math.Max(float64(res),float64(height[r]*(r-l))))r--;}}return res
}

給你一個整數數組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請你返回所有和為 0 且不重復的三元組。
注意：答案中不可以包含重復的三元組。

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。

解法1：排序+雙指針
先排序保證數據有序，這樣就不會保存重復的數組了
接下來，外層循環確定一個 i 的值，內層循環使用左右兩端向中間移動的雙指針

//每個指針移動時跳過重復元素版，力扣不友好，時間還不如不跳過的快
public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);int i=0; while(i<nums.length-2){int sum = -nums[i];int j=i+1; int k=nums.length-1;while(j<k){int cur = nums[j]+nums[k];if(cur > sum){while( j<k && nums[k]==nums[k-1])k--;k--;}else if(cur < sum){while( j<k && nums[j]==nums[j+1])j++;j++;}else{List<Integer> tmp = new ArrayList<>();tmp.add(nums[i]);tmp.add(nums[j]);tmp.add(nums[k]);res.add(tmp);while( j<k && nums[k]==nums[k-1])k--;k--;while( j<k && nums[j]==nums[j+1])j++;j++;}}while(i<nums.length-2 && nums[i+1]==nums[i])i++;i++;}return res;
}//不跳過版
public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);int i=0; while(i<nums.length-2){int sum = -nums[i];int j=i+1; int k=nums.length-1;while(j<k){int cur = nums[j]+nums[k];if(cur > sum)k--;else if(cur < sum)j++;else{List<Integer> tmp = new ArrayList<>();tmp.add(nums[i]);tmp.add(nums[j]);tmp.add(nums[k]);res.add(tmp);while(j<k&&nums[k]==nums[k-1])k--;k--;}}while(i<nums.length-2 && nums[i+1]==nums[i])i++;i++;}return res;
}

func threeSum(nums []int) [][]int {res := make([][]int,0)sort.Ints(nums)for i,v:=range nums{if i==len(nums)-2 {break}if i>0&&nums[i]==nums[i-1] {continue}target := -v;l,r := i+1,len(nums)-1for l<r {sum := nums[l]+nums[r]if sum>target{for l<r&&nums[r]==nums[r-1]{r--}r--;}else if sum<target{for l<r&&nums[l]==nums[l+1]{l++}l++}else{res = append(res,[]int{v,nums[l],nums[r]})for l<r&&nums[l]==nums[l+1]{l++}l++}}}return res
}

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。

解法1：最大前綴+最大后綴
對于每一個柱子能接的水，取決于：

1. 當前柱子高度h0
2. 當前柱子左側最高的柱子h1，當前柱子右側最高的柱子h2，取二者最小的值
3. 當前柱子能接的水為：min(h1,h2)-h0

public int trap(int[] height) {int len = height.length;int pre[] = new int[len];int suf[] = new int[len];pre[0] = height[0];for(int i=1; i<len; i++){pre[i] = Math.max(pre[i-1],height[i]);}suf[len-1] = height[len-1];for(int i=len-2; i>=0; i--){suf[i] = Math.max(suf[i+1],height[i]);}int sum = 0;for(int i=0; i<len; i++){int low = Math.min(pre[i],suf[i]);sum += (low-height[i]);}return sum;
}

func trap(height []int) int {if len(height)<3 {return 0}leng := len(height)leftMax := make([]int,leng)rightMax := make([]int,leng)leftMax[0] = height[0]for i:=1; i<len(height); i++ {if(leftMax[i-1]>height[i]){leftMax[i] = leftMax[i-1]}else{leftMax[i] = height[i]}}rightMax[len(height)-1] = height[len(height)-1]for i:=len(height)-2; i>=0; i-- {if rightMax[i+1]>height[i] {rightMax[i] = rightMax[i+1]}else{rightMax[i] = height[i]}}res := 0for i:=0; i<len(height); i++ {var curHeight intif(leftMax[i]>rightMax[i]){curHeight = rightMax[i]}else{curHeight = leftMax[i]}res+=(curHeight-height[i])}return res
}

解法2：雙指針，解法1的節省空間的方法
解法1為了維持每個位置的左右邊界最大值，使用數組來表示，可以使用雙指針來代替數組。
每次雙指針移動之后比較最大值，小的一方先移動。

public int trap(int[] height) {int len = height.length;int res = 0;int left = 0;int right = len-1;int leftMax = 0;int rightMax = 0;while(left<=right){leftMax = Math.max(leftMax,height[left]);rightMax = Math.max(rightMax,height[right]);if(leftMax<=rightMax){res+=(leftMax-height[left++]);}else{res+=(rightMax-height[right--]);}}return res;
}

解法3：單調棧
棧內元素依然是單調遞減。

當遇到相等的時候也要出棧，但是在計算面積的時候，由于左右邊界中有一條邊界和當前計算的柱子高度相等，所以高度差是0，計算出來也沒影響。

public int trap(int[] height) {int len = height.length;Deque<Integer> stack = new ArrayDeque<>();int res = 0;for(int i=0; i<len; i++){while(!stack.isEmpty() && height[stack.peek()]<=height[i]){int curIndex = stack.pop();if(stack.isEmpty()) break;int preIndex = stack.peek();res+=((i-1-preIndex)*(Math.min(height[preIndex],height[i])-height[curIndex]));}stack.push(i);}return res;
}