leetcode刷题

发表于 | 更新于 | 分类于

1、121. Best Time to Buy and Sell Stock

题目：从一个价格数组中，选择一个价格买入，另一个价格卖掉，求取得的最大利润值。（只允许操作一次）

  • 从开始遍历数组，计算从 $[0,i]$ 区间的最小值（买入值）
  • 记录一个全局利润最大值 $max=0, min=Integer.MAX_VALUE$ 因为一开始价格可能会很大
  • 计算当前遍历到当前位置的最大值： $max = Math.max(max, price[i]-min)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
    int min = Integer.MAX_VALUE;  // 记录一个最大值表示开始的最小值
    int max = 0;
    // 每次都计算从开始到当前时刻的最大利润
    for(int price:prices){
        min = Math.min(min, price);
        max = Math.max(max, price - min);
    }
    return max;
}
// 考虑用例：
[2,4,1] == 4-2
[7,1,5,3,6,4] == 6 -1
[7,6,4,3,1] == 0

2、122. Best Time to Buy and Sell Stock II

题目：从一个价格数组中，可以任意买卖多次，但是，不能连续买，只允许在买入之后再卖掉，也可以当天卖了再买入。这样的话相当于：今日没有操作，

题解：这道题由于可以无限次买入和卖出。我们都知道炒股想挣钱当然是低价买入高价抛出，那么这里我们只需要从第二天开始，如果当前价格比之前价格高，则把差值加入利润中，因为我们可以昨天买入，今日卖出，若明日价更高的话，还可以今日买入，明日再抛出。 

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
    int res = 0;
    for(int i=1;i<prices.length;i++){
        if(prices[i] > prices[i-1]){
            res += prices[i] - prices[i-1];
        }
    }
    return res;
}

3、309. Best Time to Buy and Sell Stock with Cooldown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//方法一：
// 保存两个DP数组，一个用来存 cooldown，一个用来存 sell
// sell[i] 表示 在第i天卖出，获得的最大收益
// cooldown[i] 表示 在第i天不操作，获得的最大收益
// 因为我们不可能从 第i天 买入 获得到最大收益

/* Method 1, time O(n ^ 2), space O(n)
 * 1. update cooldown[i] is easy, cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
 * 2. for update sell[i], need to scan j from 0 -> i - 1, sell[i] will be the maximum of cooldown[j - 1] + (prices[i] - prices[j])
 * means cooldown at day j - 1, and buy at day j, and sell at day i;
 * 3. Pay attention to the boundy conditon, when j == 0, cooldown[j - 1] is not defined, use 0 instead
 * 4. The maximum profit is either sell[n - 1] or cooldown[n - 1];
 */
public int maxProfit(int[] prices) {
    if(prices.length <= 0){
        return 0;
    }
    int [] sell = new int[prices.length];
    int [] cooldown = new int[prices.length];
    
    for(int i=1;i<prices.length;i++){
        cooldown[i] = Math.max(cooldown[i-1], sell[i-1]);
        for(int j=0;j<i;j++){
            if(j == 0){
                sell[i] = Math.max(sell[i], 0+prices[i]-prices[j]);
            }else{
                sell[i] = Math.max(sell[i], cooldown[j-1]+prices[i]-prices[j]);
            }
        }
    }
    return Math.max(sell[prices.length-1], cooldown[prices.length-1]);
}

/* Method 2, time O(n), space O(n)
 * In the previous method, for updating sell[i], we need to scan from 0 -> i - 1, but if you pay attention to the transition expression, 
 * all we need is the maximum of cooldown[j - 1] - prices[j] from j = 0 -> j= i - 1, 
 * so we can use a variable diff to store this value, to avoid the loop;
 * then the time expense will be just O(n)...
 */
public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    int n = prices.length;
    int[] sell = new int[n];
    int[] cooldown = new int[n];
    int diff = -prices[0];
    for (int i = 1; i < n; i++) {
        cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
        sell[i] = Math.max(sell[i], prices[i] + diff);
        diff = Math.max(diff, cooldown[i - 1] - prices[i]);
    }
    return Math.max(sell[n - 1], cooldown[n - 1]);
}

/* Method 3, time O(n), space O(1)
 * If you take a look at method 2, when we update cooldown[i] or sell[i], we only need variable from i - 1;
 * thus there is no need to store the whole array, we can just use two variables to store the data
 * so the space cost wil be O(1)
 */
 public int maxProfit(int[] prices) {
    if(prices.length <= 0){
        return 0;
    }
    int sell = 0;
    int cooldown = 0;
    int diff = -prices[0];
    
    for(int i=1;i<prices.length;i++){
        int temp = cooldown;
        cooldown = Math.max(temp, sell);
        sell = Math.max(sell, diff+prices[i]);
        diff = Math.max(diff, temp-prices[i]);
    }
    return Math.max(sell, cooldown);
}
// 精简一个常数项
public int maxProfit(int[] prices) {
    int cooldown = 0;
    int sell = 0;
    for(int i=1;i<prices.length;i++){
        int temp = cooldown;
        cooldown = Math.max(temp+prices[i]-prices[i-1], sell);
        sell = Math.max(temp, sell);
    }
    return Math.max(sell, cooldown);
}

4、714. Best Time to Buy and Sell Stock with Transaction Fee

题目：可以在任何时刻买卖（买之前必须卖掉），每买卖一次都有手续费 fee 思路：在任一时刻，有以下操作

  • buy： 买入 i
  • hold: 持有 i
  • skip: 持有0，什么也不做，跳过
  • sell: 卖出 i

则有以下递推关系：

  • buy[i] = max{skip[i-1], sell[i-1]} - prices[i] 表示：i-1时刻没有，什么也不做， i-1 卖出。i时刻买入
  • hold[i] = max{hold[i-1], buy[i-1]}
  • skip[i] = max{skip[i-1], sell[i-1]}
  • sell[i] = max{buy[i-1], hold[i-1]} + prices[i] -fee

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int maxProfit(int[] prices, int fee) {
    if(prices.length <=0) return 0;
    int [] buy = new int[prices.length];
    int [] hold = new int[prices.length];
    int [] skip = new int[prices.length]; // do nothing with no stock
    int [] sell = new int[prices.length];
    
    buy[0] = -prices[0];
    hold[0] = -prices[0];
    
    for(int i=1;i<prices.length;i++){
        buy[i] = Math.max(sell[i-1], skip[i-1]) - prices[i];
        hold[i] = Math.max(buy[i-1], hold[i-1]);
        skip[i] = Math.max(skip[i-1], sell[i-1]);
        sell[i] = Math.max(buy[i-1], hold[i-1]) + prices[i] - fee;
    } 
    int n = prices.length -1;
    return Math.max(buy[n], Math.max(hold[n], Math.max(skip[n], sell[n])));
    }
    
//方法二，只保留两个数组
/*
* buy[i] 表示 当前拥有一只股票：（上一时刻买的，这一时刻什么也不做，上一时刻卖掉，这个时刻又买的）（当前持有股票）
* sell[i] 表示 当前没有股票：（上一时刻卖的，上一时刻买的，这个时刻卖的）（当前不持有股票）
*/
public int maxProfit(int[] prices, int fee) {
    if(prices.length <=0) return 0;
    int [] buy = new int[prices.length];
    int [] sell = new int[prices.length];
    buy[0] = -prices[0];
    for(int i=1;i<prices.length;i++){
        buy[i] = Math.max(buy[i-1], sell[i-1]-prices[i]);
        sell[i] = Math.max(sell[i-1], buy[i-1]+prices[i]-fee);
    } 
    return Math.max(buy[prices.length-1], sell[prices.length-1]);
}

5、300. Longest Increasing Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
 * 	最长递增子序列
 *  F[i] 的定义是：递增子序列以 arr[i] 结束时它的最长长度
 *  F[1] = 1
 *  F[i] = max{1, F[j]+1}，如果j<i && F[i]>=F[j]
 *  input : [10,9,2,5,3,7,101,18]
 *  output: 4
 */
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if(n == 0){
    	return 0;
    }
    int [] a = new int[n];
    for(int i=0;i<n;i++){
    	a[i] = 1;
    }
    int max = a[0];
    for(int i=1;i<n;i++){
    	for(int j=0;j<i;j++){
    		a[i] = Math.max(a[i], nums[i] > nums[j]?(1 + a[j]):a[i]);
    		max = Math.max(max, a[i]);
    	}
    }
	return max;
}

6、最长公共子序列 （LCS）

对于两个子序列 S1 和 S2，找出它们最长的公共子序列。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 
 * 最长公共子序列
 * dp[i][j] 的定义是： s1字符串以i结尾，s2字符串以j结尾的最长公共子序列的长度
 * dp[i][0] = dp[0][j] = 0
 * dp[i][j] = dp[i-1][j-1] + 1, 如果 s1[i] == s2[j]
 * dp[i][j] = max{dp[i-1][j], dp[i][j-1]}，如果 s1[i] != s2[j]
 */
public static void lcs(String s1, String s2){
	int n1 = s1.length(),n2 = s2.length();
	int[][] dp = new int[n1+1][n2+1];
	for(int i=1;i<=n1;i++){
		for(int j=1;j<=n2;j++){
			if(s1.charAt(i-1)==s2.charAt(j-1)){
				dp[i][j] = dp[i-1][j-1] +1;
			}else{
				dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	System.out.println(dp[n1][n2]);
}

7、0-1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 0-1 背包问题 (容量为N，)
 * dp[i][j] 表示：前i件物品，体积不超过j的情况下能达到的最大价值
 * 第 i 件物品体积为 w,价值为 v，第i件物品是否个添加到背包中
 * 1、 不添加，dp[i][j] = dp[i-1][j] (体积不超过j的前 i-1件物品就是总价值)
 * 2、 添加，  dp[i][j] = dp[i-1][j-w] + v
 * dp[i][j] = max{dp[i-1][j], dp[i-1][j-w] + v}, 如果 j>w
 */
// n 表示 n件物品， w表示剩余重量
public static void knapsack(int w, int n, int[] weights, int [] values){
	int [][] dp = new int[n][w];
	for(int i=0;i<n;i++){
		int weight = weights[i];
		int value = values[i];
		for(int j=0;j<w;j++){
			if(j >= weight){
				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w] + value);
			}else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	System.out.println(dp[n-1][w-1]);
}

9、滑动窗口算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
 * 题目：
 * 给定一个数组[3,1,2,1] 和一个数字k，求这个数组的一个最长连续子数组，这个最长连续数组中所有的数字和必须小于或等于 k
 * 例如: {3,1,2,1}, 连续子数组 {3}{1}{2}{1} {3,1}{1,2}{2,1} {3,1,2}{1,2,1} {3,1,2,1}
 * 复合条件的只有 {1,2,1}
 * 方法一：循环迭代法
 * 分别计算  [3] [3,1] [3,1,2] [3,1,2,1]       各自的和
 *              [1]   [1,2]   [1,2,1]          各自的和
 *                  [2]     [2,1] 
 *                       [1]
 */
public static void targetSum(int [] arr, int target){
	int [][] ts = new int[arr.length][arr.length];
	for(int i=0;i<arr.length;i++){
		for(int j=i;j<arr.length;j++){
			if(i==0 && j==0){
				ts[i][j] = arr[j];
			}else{
				ts[i][j] = ts[i][j-1] + arr[j];
			}
		}
	}
	
	int result = 0;
	for(int i=0;i<arr.length;i++){
		for(int j=i;j<arr.length;j++){
			if(ts[i][j] <= target){
				result = Math.max(result, Math.max(i-j, j-i)+1);
			}
		}
	}
	System.out.println(result);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * 方法二：滑动窗口
 * 滑动窗口: {1,2,1,3,1,1,1}
 * 解题思路：
 *        1,   2, 1,    3,    1,    1,    1,    1
 *  sum   1, 1+2, 1+2+1,2+1+3,1+3+1,3+1+1,1+1+1,1+1+1+1 
 *  sum_r 1,   3, 4,    6,   ,5,    5,    3,    4
 *  len   1,   2, 3,    3,   ,3    ,3    ,3,    4   
 */ 
public static void targetK(int [] arr, int target){
	int [] tk_sum = new int[arr.length];
	int [] tk_len = new int[arr.length];
	int j = 0;
	for(int i=0;i<arr.length;i++){
		if(i==0){
			tk_sum[i] = arr[i];
			tk_len[i] = 1;
		}else{
			int sum = tk_sum[i-1] + arr[i];
			// 改变窗口大小
			if(sum > target){
				sum = sum - arr[j++];
				tk_sum[i] = sum; 
				tk_len[i] = tk_len[i-1];
			}else{
				tk_sum[i] = sum;
				tk_len[i] = tk_len[i-1] + 1;
			}
		}
	}
	int result = 0;
	for(int i=0;i<arr.length;i++){
		if(tk_sum[i] >= 4){
			result = Math.max(result, tk_len[i]);
		}
	}
	System.out.println(result);

10、72. Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * 编辑距离：从一个字符串转变到另一个字符串需要的变换步骤，共有三种变换方式：1、插入一个字符串；2、删除一个字符串；3、替换一个字符串
 * dp[i][j] 定义为： s1的前i个字符转换到s2的前j个字符需要转换的步骤
 * 递推公式： 
 * 1、当 s1 s2有一个长度为0，编辑距离就是另一个的长度
 * 2、dp[i][j] = dp[i-1][j-1] if s1[i] = s2[j] 
 * 3、else：dp[i][j] = min{a,b,c}
 *   a = dp[i-1][j] + 1， 表示s2[j+1]加上 s1[i] 然后  删除s1[i] 和 s2[j+1] === 删除 s1[i]
 *   b = dp[i][j-1] + 1, 表示s1[i+1]加上s2[j] 然后  删除s1[i+1] 和 s2[j] === 删除 s2[j]
 *   c = dp[i-1][j-1] + 1, 表示 s1[i] 和 s2[j] 替换成同一个字符，然后  删除 s1[i] 和 s2[j]
 *   
 * 优化方案：dp 二维数组 可以简化成两行， 原因是 当前j只依赖与前一行的数据 pre[] current[]
 *  1、初始化：dp[0][j] = j 
 *  2、递归：   for i in len(s1):  current[0] = j
 *   if s1[j] == s2[i]:
 *     dp[i-1][j-1] = pre[j-1]
 *   else:
 *     dp[i-1][j] = pre[j]
 *     dp[i][j-1] = current[j-1]
 *     dp[i-1][j-1] = pre[j-1]
 *     
 * 优化方案2： dp采用一维数组，原因是i的状态之和左，上和左上的状态有关 （根据递推公式改进，略过）
 */
public static void EditDistance(String s1, String s2){
	int [][] dp = new int[s1.length()+1][s2.length()+1];
	if(s1.length() == 0 || s2.length() == 0){
		System.out.println(Math.max(s1.length(), s2.length()));
	}
	for(int i=0;i<=s1.length();i++){
		dp[i][0] = i;
	}
	for(int i=0;i<=s2.length();i++){
		dp[0][i] = i;
	}
	for(int i=1;i<=s1.length();i++){
		for(int j=1;j<=s2.length();j++){
			if(s1.charAt(i-1) == s2.charAt(j-1)){
				dp[i][j] = dp[i-1][j-1];
			}else{
				dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
			}
		}
	}
	System.out.println(dp[s1.length()][s2.length()]);
}

11、135. Candy

题目：n个人，每人有一个rating值，在满足每个人至少一个糖对于任意相邻的两个人，rating值高的人分到的糖也多的情况下，最少需要多少糖。 

1
2
3
4
5
6
Input: [1,0,2]
Output: 5
Input: [1,2,2]
Output: 4
Input: [1,3,5,3,2,4]
Output: 11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
 * 首先考虑简单情况，即单调的时候：
 * 对于单调递增的情况，比如[1,3,4,6,9]，这个时候只要从左到右扫一下，
 * 第一个人给1个，第二个人2个，以此类推。
 * 对于单调递减的情况，比如[9,6,4,3,1]，这个时候只要从右到左扫一下，  * 最后一个人一个，倒数第二个人2个，以此类推。
 * 对于比较复杂的情况，我们可以先从左到右扫一遍，类似递增的做法，更  * 新值；然后从右到左扫一遍，类似于递减的做法，更新值。
 * 例如： yi以[1,3,5,3,2,4]为例子，首先从左到右扫一遍，得到[1,2,3,1,1,2]，然后从右到左扫一遍，得到[1,2,3,2,1,2]
 * 从左到右，ratings[i] > ratings[i-1], arr[i] = arr[i] + 1
 * 从右到做，ratings[j] > ratings[j+1], arr[j] = Max(arr[j], arr[j+1]+1)
*/
public int candy(int[] ratings) {
    int [] arr = new int[ratings.length];
    arr[0] = 1;
    for(int i=1;i<ratings.length;i++){
        if(ratings[i] > ratings[i-1]){
            arr[i] = arr[i-1] + 1;
        }else{
            arr[i] = 1;
        }
    }
    for(int j=ratings.length-2;j>=0;j--){
        if(ratings[j] > ratings[j+1]){
            arr[j] = Math.max(arr[j], arr[j+1] + 1);
        }
    }
    int res = 0;
    for(int r:arr){
        res += r;
    }
    return res;
}

12、50. Pow(x, n)，快速幂计算 $x^n$ （数字分解为二进制）

题解：n可以用二进制来表示，比如3表示为11,11表示为1011等，分解为 $2^0+2^1+2^2...$ 

1
2
3
4
5
6
7
8
9
10
public static int FastPower(int a,int b){  
    int ans = 1,base = a;  
    while(b != 0){  
        if((b&1) != 0)  // 对应位置是1，否则为0
            ans *= base;  
        base*=base;  
        b >>= 1;  // 右移除以2  
    }  
    return ans; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Input: 2.00000, 10
Output: 1024.00000

Input: 2.10000, 3
Output: 9.26100

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
n = [−231, 231 − 1]

 // 题解
 public double myPow(double x, int n) {
    double res = 1.0;
    double base = x;
    if(n == -2147483648){
        n = 0 - n/2;
        base = 1/(x*x);
    }else if(n < 0){
        base = 1/x;
        n = 0-n;
    }
    while(n != 0){
        if((n&1) != 0){
            res *= base;
        }
        base *= base;
        n = n >> 1;
    }
    return res;
}

13、蓄水池（42. Trapping Rain Water）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// 方法一： water[i] 表示第i个上面可以储存多少水
// 递推： water[i] = Max{0, Min{Max[0,...,i-1], Max[i+1,...,n-1]} - arr[i]}
// 从0到i-1 的最大值，从i+1到n-1的最大值，其中最小值 减去 i位置的值，就是可以存水的值
// 时间复杂度 O(N*N)
public int trap(int[] height) {
    int [] water = new int[height.length];
    for(int i=1;i<height.length-1;i++){
        int leftMax = height[0];
        for(int j=0;j<i;j++){
            if(leftMax < height[j]){
                leftMax = height[j];
            }
        }
        int rightMax = height[i+1];
        for(int k=i+1;k<height.length;k++){
            if(rightMax < height[k]){
                rightMax = height[k];
            }
        }
        water[i] = Math.max(0, (Math.min(leftMax, rightMax)-height[i]));
    }
    int res = 0;
    for(int i=0;i<water.length;i++){
        res += water[i];
    }
    return res;
}

// 方法二，预处理，提前准备好两个数组，left和right，分别表示从 从左到i位置的最大值，和从i开始到最后的最大值
// 递推： water[i] = Math.max(0, (Math.min(left[i-1], right[i+1])-height[i]));
public int trap(int[] height) {
    int n = height.length;
    if(n == 0) return 0;
    int [] water = new int[n];
    int [] left = new int[n];
    int [] right = new int[n];

    left[0] = height[0];
    right[n-1] = height[n-1];
    
    for(int i=1;i<n;i++){
        left[i] = Math.max(height[i], left[i-1]);
    }
    
    for(int j=n-2;j>=0;j--){
        right[j] = Math.max(height[j], right[j+1]);
    }
    
    for(int i=1;i<n-1;i++){
        water[i] = Math.max(0, (Math.min(left[i-1], right[i+1])-height[i]));
    }
    
    int res = 0;
    for(int i=0;i<water.length;i++){
        res += water[i];
    }
    return res;
}

// 方法三，优化left数组为一个变量，因为在遍历的时候，left[i] 是可以算出来的
public int trap(int[] height) {
    int n = height.length;
    if(n == 0) return 0;
    int [] water = new int[n];
    int left = height[0];
    int [] right = new int[n];

    right[n-1] = height[n-1];        
    for(int j=n-2;j>=0;j--){
        right[j] = Math.max(height[j], right[j+1]);
    }
    for(int i=1;i<n-1;i++){
        water[i] = Math.max(0, (Math.min(left, right[i+1])-height[i]));
        if(height[i] > left){
            left = height[i];
        }
    }
    int res = 0;
    for(int i=0;i<water.length;i++){
        res += water[i];
    }
    return res;
}
//方法四：用仅有个几个变量来实现
// 考虑 5 [4] ... 3 7 这个数组，此时4所处位置，其储藏水量为：Max{leftMax-4, 0} 因为 leftMax < rightMax
// 考虑 8 4 ... [3] 7 这个数组，此时3所处位置，其储藏水量为：Max{rightMax-3, 0} 因为 leftMax > rightMax
// 这样递推下去，就可以直接得到结果
public int trap(int[] height) {
    if(height == null || height.length < 3) return 0;
    int value = 0;
    int leftMax = height[0];
    int rightMax = height[height.length-1];
    
    int l = 1;
    int r = height.length-2;
    
    while(l <= r){
        if(leftMax <= rightMax){
            value += Math.max(0, leftMax - height[l]);
            leftMax = Math.max(leftMax, height[l++]);
        }else{
            value += Math.max(0, rightMax - height[r]);
            rightMax = Math.max(rightMax, height[r--]);
        }
    }
    return value;
}

14、蓄水池（11. Container With Most Water）

1
2
3
4
5
6
7
8
9
10
11
12
// 双指针 left++； right--; 不断计算最大值
public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int res = 0;
    while(left < right){
        res = Math.max(res, (right-left)*(Math.min(height[left], height[right])));
        if(height[left] < height[right]) left++;
        else right--;
    }
    return res;
}