题解 | #盛水最多的容器#
盛水最多的容器
https://www.nowcoder.com/practice/3d8d6a8e516e4633a2244d2934e5aa47
一个思路不同的贪心
经典贪心思路是：当前要挪动一个指针，那么宽度必然减少1，既然宽度减少量是固定的，我们选择短的一边挪动，期待挪动后的木板会变长。
我的方法是，相比于把木板当作主体，我把水当作主体，给木板分配任务。我们知道，盛水量最大的时候，水面有可能是任何高度：可能是相距比较远的短板，也可能是相距比较近的长板。我们可以从水的高度出发，当水的高度为h时，找出能存最多水的两块木板，h = 1, 2, 3...n。在固定高度的情况下，能乘最多水的两块木板需要满足先后两个条件：
- 两块木板的高度都大于等于h
- 两块木板之间的距离尽可能的远
那么我们就可以开始贪心了：
- 首先设置最左和最右两个指针
- 当前需要装的水的高度设定为1
- 判断若左板高度不够1，那么挪动左板直到它能胜任；反之若右板无法胜任，挪动右板
- 若两板高度都满足了，这便是当前水高度下的最大盛水量，我们把它记录下来
- 将水面高度升高1，继续从第3步开始循环直到两个指针相遇
public int maxArea (int[] height) {
int i = 0, j = height.length - 1;
int h = 1, max = 0;
while (i < j) {
if (height[i] < h) { // 左板不达标
i++;
} else if (height[j] < h) { // 右板不达标
j--;
} else {
max = Math.max(h++ * (j - i), max); // 记录水高度为h时的最大盛水量
}
}
return max;
}
投递小鹏汽车等公司10个岗位
