移动0
给定一个数组 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 := 0
for i,_ := range nums{
if nums[i]!=0{
tmp := nums[slow]
nums[slow] = nums[i]
nums[i] = tmp
slow++
}
}
}
解法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)-1
res := 0
for 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)-1
for 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：最大前缀+最大后缀
对于每一个柱子能接的水，取决于：
- 当前柱子高度h0
- 当前柱子左侧最高的柱子h1，当前柱子右侧最高的柱子h2，取二者最小的值
- 当前柱子能接的水为：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 := 0
for i:=0; i<len(height); i++ {
var curHeight int
if(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;
}
