柱子
接水
11. 盛最多水的容器 mid
给定一个长度为 n 的整数数组 height。有 n 条垂线, 第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
You are given an integer array height of length n.
There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水。
Find two lines that together with the x-axis form a container, such that the container contains the most water.
返回容器可以储存的最大水量。
Return the maximum amount of water a container can store.
说明：你不能倾斜容器。
Notice that you may not slant the container.
短板决定了面积, 将短的那一侧向中间移动; 如果两边一样长, 那么只移动一侧面积都不会更大, 所以移动两端
class Solution {
public int maxArea(int[] height) {
int p1 = 0, p2 = height.length - 1;
int res = 0;
while (p1 < p2) {
int square;
if (height[p1] < height[p2])
square = height[p1] * (p2 - p1++);
else if (height[p1] > height[p2])
square = height[p2] * (p2-- - p1);
else
square = height[p1] * (p2-- - p1++);
res = Math.max(res, square);
}
return res;
}
}func maxArea(height []int) int {
l,r := 0,len(height)-1
res := 0
for l < r {
res = max(res, min(height[l],height[r])*(r-l))
if height[l] < height[r] {
l++
} else if height[l] > height[r] {
r--
} else {
l++
r--
}
}
return res
}
func min (a int, b int) int {
if a < b {
return a
}
return b
}
func max (a int, b int) int {
if a > b {
return a
}
return b
}42. 接雨水 hard
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图, 计算按此排列的柱子, 下雨之后能接多少雨水。
解法 1: 单调栈
要模拟去想, 遍历过程中, 当前元素首先作为右端参与计算, 然后作为左端入栈;
如果当前元素比前一个元素高 & 前一个元素前面还有, 计算面积;
class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && height[i] > height[stack.element()]) {
int t1 = stack.pop();
if (stack.isEmpty()) break;
int t2 = stack.element();
int currWidth = i - t2 - 1;
int currHeight = Math.min(height[t2], height[i]) - height[t1];
res += currWidth * currHeight;
}
stack.push(i);
}
return res;
}
}解法 2: 动态规划-前缀函数
跟 3 元组有点像, 用前缀函数记录前后的最大值, 就能计算当前柱子的积水
class Solution {
public int trap(int[] arr) {
int n = arr.length;
int res = 0;
int[] heigh = new int[n];
heigh[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
heigh[i] = Math.max(arr[i], heigh[i + 1]);
}
int pre = arr[0];
for (int i = 1; i < n - 1; i++) {
int diff = Math.min(pre, heigh[i + 1]) - arr[i];
res += Math.max(diff, 0);
pre = Math.max(pre, arr[i]);
}
return res;
}
}解法 3: 双指针
利用当前柱子积水由左右两侧高值的较小一方决定, 可以维护双指针和 2 个最大值(表示双指针左右两侧的最大值)
迭代过程中, 最大值较小的一侧可以计算该指针所指向柱子的积水; 相反的一侧因为不知道中间是否有更高的柱子, 所以不能计算
class Solution {
public int trap(int[] arr) {
int n = arr.length;
int res = 0;
int l = 1, r = n - 2;
int lmax = arr[0], rmax = arr[n - 1];
while (l <= r) {
if (lmax < rmax) {
res += Math.max(0, lmax - arr[l]);
lmax = Math.max(lmax, arr[l]);
l++;
} else {
res += Math.max(0, rmax - arr[r]);
rmax = Math.max(rmax, arr[r]);
r--;
}
}
return res;
}
}407. 接雨水 II hard
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
解法
从最外缘一圈入优先队列, 出队的元素决定了相邻 4 向柱子的积水, 入队要入 max(水位,柱子高度)
class Solution {
public int trapRainWater(int[][] heightMap) {
if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) return 0;
int rowCnt = heightMap.length;
int colCnt = heightMap[0].length;
// [0]=r [1]=c [2]=水位/柱子高度
PriorityQueue<int[]> que = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
for (int r = 0; r < rowCnt; r++) {
que.add(new int[]{r, 0, heightMap[r][0]});
que.add(new int[]{r, colCnt - 1, heightMap[r][colCnt - 1]});
heightMap[r][0] = -1;
heightMap[r][colCnt - 1] = -1;
}
for (int c = 1; c < colCnt - 1; c++) {
que.add(new int[]{0, c, heightMap[0][c]});
que.add(new int[]{rowCnt - 1, c, heightMap[rowCnt - 1][c]});
heightMap[0][c] = -1;
heightMap[rowCnt - 1][c] = -1;
}
int res = 0;
int[] dr = {1, -1, 0, 0};
int[] dc = {0, 0, 1, -1};
while (!que.isEmpty()) {
int[] point = que.remove();
int tmpR = point[0];
int tmpC = point[1];
int tmpH = point[2];
for (int k = 0; k < 4; k++) {
int newR = tmpR + dr[k];
int newC = tmpC + dc[k];
if (newR >= 0 && newR < rowCnt
&& newC >= 0 && newC < colCnt
&& heightMap[newR][newC] != -1) {
// 入队就计算
res += Math.max(0, tmpH - heightMap[newR][newC]);
que.add(new int[]{newR, newC, Math.max(tmpH, heightMap[newR][newC])});
heightMap[newR][newC] = -1;
}
}
}
return res;
}
}柱子面积
84. 柱状图中最大的矩形 hard
LCR 039. 柱状图中最大的矩形
给定 n 个非负整数, 用来表示柱状图中各个柱子的高度。每个柱子彼此相邻, 且宽度为 1。
求在该柱状图中, 能够勾勒出来的矩形的最大面积。
解法 单调栈
找到元素 i 左右比 i 低的元素索引
class Solution {
public int largestRectangleArea(int[] h) {
int n = h.length;
int[] left = new int[n];
int[] right = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
// 如果没 pop, 说明 right[i] = n-1
Arrays.fill(right, n - 1);
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && h[i] < h[stack.element()]) {
right[stack.pop()] = i - 1;
}
if (!stack.isEmpty()) left[i] = stack.element() + 1;
stack.push(i);
}
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, h[i] * (right[i] - left[i] + 1));
}
return max;
}
}