6.2 栈应用

如果数据的保存顺序和使用顺序相反, 具有后进先出的特点, 可以考虑使用栈来解决.

6.2.1 问题36: 后缀表达式

LCR 036. 逆波兰表达式求值

根据 逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

6.2.1.1 分析&题解

golang 没有stack 标准库, 可以使用切片来模拟栈.

注意除法和减法是有先后顺序的, 后入栈的为除数

时间复杂度: O(n), 遍历数组

空间复杂度: O(n), 需要栈中可能有n个操作数

func evalRPN(tokens []string) int {
    stack := make([]int, 0)
    for _, t := range tokens {
       num, err := strconv.Atoi(t)
       if err == nil {
          // 数字入栈
          stack = append(stack, num)
       } else { // 符号, 则数字出栈
          a, b := stack[len(stack)-2], stack[len(stack)-1]
          stack = stack[:len(stack)-2]
          switch t {
          case "+":
             stack = append(stack, a+b)
          case "-":
             stack = append(stack, a-b)
          case "*":
             stack = append(stack, a*b)
          case "/":
             stack = append(stack, a/b)
          }
       }
    }

    return stack[len(stack)-1]
}

6.2.2 问题37: 行星碰撞

LCR 037. 行星碰撞

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

示例 4：

输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。 

提示：

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

6.2.2.1 分析

1. 若行星向右飞行, 则入栈
2. 若行星向左飞行, 栈顶元素向右, 那么则进行碰撞. 若和所有的栈顶元素碰撞之后没有消失, 则该元素入栈

6.2.2.2 题解

每个行星只能出栈入栈一次, 时间复杂度为 O(n)

空间复杂度 O(n)

func asteroidCollision(asteroids []int) []int {
	// 栈
	stack := make([]int, 0)

	for _, a := range asteroids {
		alive := true
		for alive && a < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
			alive = stack[len(stack)-1] < -a // 当前元素是否存活
			if stack[len(stack)-1] <= -a {   // 栈顶爆炸
				stack = stack[:len(stack)-1]
			}
		}
		if alive {
			stack = append(stack, a)
		}
	}

	return stack
}

6.2.3 问题38: 每日温度

LCR 038. 每日温度

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

6.2.3.1 分析

将每日温度入栈, 如果当前温度大于栈顶温度, 表示遇到了最近的一次高温, 则出栈. 之后继续和栈顶元素比较, 直到当前温度入栈为止.

流程:

1. 遍历数组
2. 当前温度和栈顶对比, 大于则栈顶温度出栈, 计算天数差. 继续和下一个栈顶元素比较, 直到自身入栈

6.2.3.2 题解

时间和空间复杂度均为 O(n)

func dailyTemperatures(temperatures []int) []int {
    // 栈
    stack := make([]int, 0, len(temperatures))

    result := make([]int, len(temperatures))
    for i, t := range temperatures {
       for len(stack) > 0 && t > temperatures[stack[len(stack)-1]] { // 出栈条件
          prev := stack[len(stack)-1]
          stack = stack[:len(stack)-1]
          result[prev] = i - prev // 天数差
       }

       stack = append(stack, i)
    }

    return result
}

6.2.4 问题39: 直方图的最大矩形面积

LCR 039. 柱状图中最大的矩形

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

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

示例 1:

img

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

img

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

6.2.4.1 分析&题解

计算矩形的面积需要知道, 长和宽.

对于柱子i和j, 其宽为$j-i+1$, 高为柱子之间最矮的高度.

那么问题就转化成了在两个柱子之间寻找最矮的柱子高度, 计算所有的可能面积后找出最大的那个.

暴力解法

遍历数组, 找出所有的矩形, 得出最大面积. TC: $O(n^2)$, SC: $O(1)$

package ofstack

func largestRectangleAreaBruteForce(heights []int) int {
	maxArea := 0

	for i := 0; i < len(heights); i++ {
		minHeight := heights[i]
		for j := i; j < len(heights); j++ {
			minHeight = min(minHeight, heights[j])
			area := (j - i + 1) * minHeight
			maxArea = max(maxArea, area)
		}
	}

	return maxArea
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

分治法

若以整个数组最小高度$N_i$为界, 可将问题分解成三个部分:

1. 以$N_i$为高的最大矩形面积 $A_i$
2. $N_i$ 左侧的最大矩形面积, 即 $N_0,N_1, ..., N_{i-1}$ 部分的最大矩形面积 $A_l$
3. $N_i$右侧的最大矩形面积, 即 $N_{i+1}, N_{i+2}, ..., N_{n}$ 部分的最大矩形面积 $A_r$

那么最终结果就是, 三者中最大的那个.

三部分的计算方式完全相同, 那么可以使用递归的方式进行计算.

最好情况: 每次都能将直方图划分成$\frac{n}{2}$, 则 TC: O(nlogn), SC: 递归深度 $O(logn)$

最差情况: 每次最矮高度都在直方图的一侧(数组有序), TC: $O(n^2)$, SC: 递归深度 O(n)

func largestRectangleAreaRecursion(heights []int) int {
	return largestArea(heights, 0, len(heights))
}

func largestArea(heights []int, start, end int) int {
	// 递归出口
	if start == end {
		return 0
	}
	if start+1 == end {
		return heights[start]
	}

	// 寻找最低高度
	minIdx := start
	for i := start + 1; i < end; i++ {
		if heights[i] < heights[minIdx] {
			minIdx = i
		}
	}
	minHeight := heights[minIdx]
	area := (end - start) * minHeight            // 中间
	left := largestArea(heights, start, minIdx)  // 左边
	right := largestArea(heights, minIdx+1, end) // 右边

	area = max(area, left)
	return max(area, right)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

• 需要注意递归出口的条件
• 区间为左闭右开, [start, end)

单调栈

扫描每个柱子

• 若当前柱子高度大于栈顶柱子高度, 则入栈
• 若小于, 则栈顶元素出栈, 计算最大矩形面积; 然后继续比较栈顶元素, 直到大于栈顶元素, 入栈

此流程的效果相当于, 对于栈顶柱子 $N_i$, 同时向左向右扩展, 直到遇到高度小于它的柱子, 那么当前最大的矩形面积即可得出.

一次扫描之后, 相当于算出了所有柱子对应的最大面积, 只需找出最大的即可.

func largestRectangleAreaStack(heights []int) int {
	stack := make([]int, 0, len(heights))
	// 假设最左边有个的柱子, 方便计算最矮柱子对应的最大矩形
	stack = append(stack, -1)

	maxArea := 0
	for i := range heights {
		// 出栈条件
		for stack[len(stack)-1] != -1 && heights[i] <= heights[stack[len(stack)-1]] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			height := heights[idx]
			width := i - stack[len(stack)-1] - 1
			maxArea = max(maxArea, height*width)
		}
		stack = append(stack, i)
	}

	for stack[len(stack)-1] != -1 {
		i := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		h := heights[i]
		w := len(heights) - stack[len(stack)-1] - 1
		maxArea = max(maxArea, h*w)
	}

	return maxArea
}

6.2.5 问题40: 矩阵中的最大矩形

LCR 040. 最大矩形

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

**注意：**此题 matrix 输入格式为一维 01 字符串数组。

示例 1：

img

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = ["0"]
输出：0

示例 4：

输入：matrix = ["1"]
输出：1

示例 5：

输入：matrix = ["00"]
输出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 0 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

6.2.5.1 分析&题解

将矩阵从左向右看, 可将其转化成直方图, 那么解法和直方图的解法相同.

// TODO: 2023-09-11

Reference

1. 剑指Offer（专项突破版）