跟着卡哥学算法Day 49：单调栈 part2

42. 接雨水 🌟🌟#

力扣链接 🌟🌟

题目描述#

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

解题思路#

对每个柱子 i，找出其左侧最高柱子 leftMax 和右侧最高柱子 rightMax，当前柱子积水量取决于其左右两边最高柱子的较小值减去当前柱子的高度

1
Math.min(leftMax, rightMax) - height[i]

暴力法#

遍历每个位置 i，找到左边最大值和右边最大值，计算每个位置的积水量，累加总和。

左边最大值：从 0 到 i-1 中的最大值
右边最大值：从 i+1 到末尾的最大值
计算每个位置的积水量

1
var trap = function (height) {
2
  const len = height.length
3
  let total = 0
4

5
  for (let i = 1; i < len - 1; i++) {
6
    let leftMax = 0
7
    let rightMax = 0
8
    for (let j = 0; j < i; j++) {
9
      leftMax = Math.max(leftMax, height[j])
10
    }
11
    for (let j = i; j < len; j++) {
12
      rightMax = Math.max(rightMax, height[j])
13
    }
14

15
    const h = Math.min(leftMax, rightMax) - height[i]
16
    if (h > 0) total += h // 注意只有h大于零的时候，在统计到总和中
17
  }
18
  return total
19
}

暴力法：O(n^2)

双指针优化#

是对暴力法的优化，暴力法需要得到柱子 i 两边的最高高度 leftMax 和 rightMax
maxLeft 数组用于记录每个柱子 i 左边的最高高度

从左到右遍历，每个柱子的左边最大高度是：
- 当前柱子的高度 height[i] 和
- 它左边柱子的最大高度 maxLeft[i - 1] 的较大值
maxRight 数组用于记录每个柱子 i 右边的最高高度

从右到左遍历，每个柱子的右边最大高度是：
- 当前柱子的高度 height[i] 和
- 它右边柱子的最大高度 maxRight[i + 1] 的较大值

1
//双指针
2
var trap = function (height) {
3
  const len = height.length
4
  if (len <= 2) return 0 // 如果柱子数量小于等于2，无法形成积水，直接返回0
5

6
  const maxLeft = new Array(len).fill(0) // 用于记录每个柱子左边的最大高度
7
  const maxRight = new Array(len).fill(0) // 用于记录每个柱子右边的最大高度
8

9
  // 记录每个柱子左边柱子的最大高度
10
  maxLeft[0] = height[0] // 第一个柱子的左边最大高度就是它自己
11
  for (let i = 1; i < len; i++) {
12
    maxLeft[i] = Math.max(height[i], maxLeft[i - 1]) // 当前柱子的左边最大高度是它左边柱子的最大高度和它自身高度的较大值
13
  }
14

15
  // 记录每个柱子右边柱子的最大高度
16
  maxRight[len - 1] = height[len - 1] // 最后一个柱子的右边最大高度就是它自己
17
  for (let i = len - 2; i >= 0; i--) {
18
    maxRight[i] = Math.max(height[i], maxRight[i + 1]) // 当前柱子的右边最大高度是它右边柱子的最大高度和它自身高度的较大值
19
  }
20

21
  // 求和
22
  let sum = 0 // 用于记录总的积水量
23
  for (let i = 0; i < len; i++) {
24
    let count = Math.min(maxLeft[i], maxRight[i]) - height[i] // 当前柱子上方的积水量是左右两边最大高度的较小值减去当前柱子的高度
25
    if (count > 0) sum += count // 如果积水量大于0，则累加到总积水量中
26
  }
27

28
  return sum // 返回总积水量
29
}

单调栈#

与暴力法不同，单调栈是按照行来计算积水量
栈头到栈尾是递增的
- 一旦发现添加的柱子高度大于栈头元素，则出现凹槽
- 此时栈头元素就是凹槽的底部，栈头第二个元素就是凹槽的左柱子，当前元素就是凹槽的右柱子
遇到相同高度的柱子，则弹出旧的，加入新的，因为要求宽度的时候，需要有最右边的柱子来计算

处理逻辑：

当前遍历柱子高度小于栈顶元素高度 height[i] < height[stack.top()]

当前元素入栈
当前遍历柱子高度等于栈顶元素高度 height[i] == height[stack.top()]
- 需要先将旧元素出栈
- 新元素再入栈

当前遍历柱子高度大于栈顶元素高度 height[i] > height[stack.top()]

出现凹槽

弹出栈顶元素，弹出的元素就是凹槽的底部
弹出栈顶第二个元素，弹出的元素就是凹槽的左边柱子
当前元素就是凹槽的右边柱子

1
const min = stack.pop() // 弹出栈顶元素，凹槽底部
2
const left = stack[stack.length - 1] // 栈顶第二个元素，凹槽左边柱子
3
// 当前槽的高度
4
const h =
5
  Math.min(
6
    height[i],
7
    height[left] // 右边柱子和栈顶元素的较小值
8
  ) - height[mid]
9
// 当前槽的宽度 = 凹槽右边的下标 - 凹槽左边的下标 - 1
10
const w = i - left - 1
11
sum = h * w

1
var trap = function (height) {
2
  const len = height.length
3
  let total = 0
4
  const stack = []
5
  stack.push(0)
6

7
  for (let i = 1; i < len; i++) {
8
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
9
      const mid = stack.pop()
10
      if (stack.length) {
11
        const left = stack[stack.length - 1]
12
        const h = Math.min(height[i], height[left]) - height[mid]
13
        const w = i - stack[stack.length - 1] - 1 // 注意减一，只求中间宽度
14
        total += h * w
15
      }
16
    }
17
    stack.push(i)
18
  }
19

20
  return total
21
}

84.柱状图中最大的矩形 🌟🌟#

力扣链接 🌟🌟

题目描述#

给给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

解题思路#

暴力法#

对每个柱子 i，向左右扩展找到第一个比它小的左边界 left 和右边界 right，当前柱子能形成的最大矩形面积为

1
var largestRectangleArea = function (heights) {
2
  const n = heights.length
3

4
  let sum = 0
5

6
  for (let i = 0; i < n; i++) {
7
    let left = i - 1
8
    while (left >= 0 && heights[left] >= heights[i]) left--
9
    let right = i + 1
10
    while (right < n && heights[right] >= heights[i]) right++
11

12
    const w = right - left - 1
13
    sum = Math.max(sum, heights[i] * w)
14
  }
15
  return sum
16
}

双指针优化#

预处理每个柱子的左边界 left 和右边界 right，利用跳跃指针快速找到边界，避免重复遍历

1
function largestRectangleAreaOptimized(heights) {
2
  const n = heights.length
3
  if (n === 0) return 0
4
  const left = new Array(n).fill(-1)
5
  const right = new Array(n).fill(n)
6

7
  // 预处理左边界
8
  for (let i = 1; i < n; i++) {
9
    let p = i - 1
10
    while (p >= 0 && heights[p] >= heights[i]) p = left[p]
11
    left[i] = p
12
  }
13

14
  // 预处理右边界
15
  for (let i = n - 2; i >= 0; i--) {
16
    let p = i + 1
17
    while (p < n && heights[p] >= heights[i]) p = right[p]
18
    right[i] = p
19
  }
20

21
  // 计算最大面积
22
  let maxArea = 0
23
  for (let i = 0; i < n; i++) {
24
    const width = right[i] - left[i] - 1
25
    maxArea = Math.max(maxArea, heights[i] * width)
26
  }
27
  return maxArea
28
}

单调栈#

区别：单调递减栈（栈头到栈底的顺序从大到小）
遇到比栈顶小的柱子时，弹出栈顶并计算以该高度为高的矩形面积，左边界为新的栈顶，右边界为当前索引

1
function largestRectangleAreaMonotonicStack(heights) {
2
  heights = [0, ...heights, 0] // 添加哨兵简化代码
3
  let stack = []
4
  let maxArea = 0
5
  for (let i = 0; i < heights.length; i++) {
6
    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
7
      const top = stack.pop()
8
      const left = stack[stack.length - 1]
9
      const width = i - left - 1
10
      maxArea = Math.max(maxArea, heights[top] * width)
11
    }
12
    stack.push(i)
13
  }
14
  return maxArea
15
}

音乐

音乐

42. 接雨水 🌟🌟#

题目描述#

解题思路#

暴力法#

双指针优化#

单调栈#

84.柱状图中最大的矩形 🌟🌟#

题目描述#

解题思路#

暴力法#

双指针优化#

单调栈#

音乐

文章目录