Leetcode Data Structure Note

Chapter1 Stack

84. 柱状图中最大的矩形「Hard」

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

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

picture

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

pictture

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

1
2
输入: [2,1,5,6,2,3]
输出: 10

算法分析：

枚举「宽」的暴力法这里就不再过多赘述了。

我们对枚举「高」来做一些分析以及优化。

对枚举「高」的暴力法就是对每一条「高」进行中心扩展：

  • 首先我们枚举某一根柱子 $i$ 作为高 $h=height[i]$.
  • 随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 $h$，也就是说，我们需要找到左右两侧最近的高度小于 $h$ 的柱子，这两根柱子之间的所有柱子的高度均不小于 $h$，这就是 $i$ 能扩展的最远范围.

对于上述分析我们可知，我们可以使用单调栈来维护左边和右边的高度依赖关系。由分析可知，我们需要查找的是距离 $i$ 最近比 $h$ 低的柱子，所以我们可以维护一个单调递增的栈，每次只需要查找对比栈顶元素与当前的柱子高度，进行 $pop$ 操作和 $push$ 操作即可。

单调栈的算法如下：

  • 当我们枚举到第 $i$ 根柱子时，我们从栈顶不断移除 $height[j]>height[i]$ 的 $j$ 值。在移除完毕后，栈顶元素的 $j$ 值就一定满足 $height[j]<height[i]$，此时 $j$ 就是 $i$ 左侧且最近的小于其高度的柱子。
  • 这里会有一种特殊情况。如果我们移除了栈中所有的 $j$ 值，说明 $i$ 左侧所有柱子的高度都大于 $height[i]$，那么我们可以认为 $i$ 左侧且最近的小于其高度的柱子在位置 $j=-1$，它是一根「虚拟」的、高度无限低的柱子。这样的定义不会对我们的答案产生任何的影响，我们也称这根「虚拟」的柱子为「哨兵」。
  • 最后我们将 $i$ 这根柱子入栈。

Details：

我们在栈中存放的是柱子的下标而非柱子高度。

最后求面积为 maxArea = max(maxArea, (right[i] - left[i] - 1) * heights[i])，具体下标的长度需要注意。

本题还能进行常数优化 $\Rightarrow$ 一次遍历，这里就不提了

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0;
        int n = (int)heights.size();
        stack<int> min_stack;
        vector<int> left(n), right(n);
        
        for (int i = 0; i < n; ++i) {
            while (!min_stack.empty() and heights[i] <= heights[min_stack.top()]) {
                min_stack.pop();
            }
            left[i] = min_stack.empty() ? -1 : min_stack.top();
            min_stack.push(i);
        }
        
        min_stack = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!min_stack.empty() and heights[i] <= heights[min_stack.top()]) {
                min_stack.pop();
            }
            right[i] = min_stack.empty() ? n : min_stack.top();
            min_stack.push(i);
        }
        
        for (int i = 0; i < n; ++i) {
            maxArea = max(maxArea, (right[i] - left[i] - 1) * heights[i]);
        }
        return maxArea;
    }
};

503. 下一个更大元素 II「Medium」

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 $x$ 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 $-1$.

示例 1:

1
2
3
4
5
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

算法分析：

我们可以使用单调栈解决本题。单调栈中保存的是下标，从栈底到栈顶的下标在数组 $nums$ 中对应的值是单调不升的。

每次我们移动到数组中的一个新的位置 $i$，我们就将当前单调栈中所有对应值小于 $nums[i]$ 的下标弹出单调栈，这些值的下一个更大元素即为 $nums[i]$，随后我们将位置 $i$ 入栈.

但是注意到只遍历一次序列是不够的，例如序列 $[2,3,1]$，最后单调栈中将剩余 $[3,1]$，其中元素 $[1]$ 的下一个更大元素还是不知道的

一个朴素的思想是，我们可以把这个循环数组「拉直」，即复制该序列的前 $n-1$ 个元素拼接在原序列的后面。这样我们就可以将这个新序列当作普通序列，用上文的方法来处理。

而在本题中，我们不需要显性地将该循环数组「拉直」，而只需要在处理时对下标取模即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n, -1);
        stack<int> stk;
        for (int i = 0; i < n * 2 - 1; i++) {
            while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
                ret[stk.top()] = nums[i % n];
                stk.pop();
            }
            stk.push(i % n);
        }
        return ret;
    }
};

224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

示例 1：

1
2
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

  • 1 <= s.length <= 3 * 105
  • s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
  • s 表示一个有效的表达式

算法分析：

方法：括号展开 + 栈

由于字符串除了数字与括号外，只有加号和减号两种运算符。因此，如果展开表达式中所有的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号会发生变化。

因此，我们考虑使用一个取值为 {-1, 1} 的整数 $sign$ 代表「当前」的符号。根据括号表达式的性质，它的取值：

  • 与字符串中当前位置的运算符有关；
  • 如果当前位置处于一系列括号之内，则也与这些括号前面的运算符有关：每当遇到一个以 -− 号开头的括号，则意味着此后的符号都要被「翻转」。

考虑到第二点，我们需要维护一个栈 $ops$，其中栈顶元素记录了当前位置所处的每个括号所「共同形成」的符号。例如，对于字符串 $1+2+(3-(4+5))$：

  • 扫描到 $1+2$ 时，由于当前位置没有被任何括号所包含，则栈顶元素为初始值 $+1$.

  • 扫描到 $1+2+(3$ 时，当前位置被一个括号所包含，该括号前面的符号为 $+$ 号，因此栈顶元素依然 $+1$.

  • 扫描到 $1+2+(3-(4$ 时，当前位置被两个括号所包含，分别对应着 $+$ 号和 $-$ 号，由于 $+$ 号和 $-$ 号合并的结果为 $-$ 号，因此栈顶元素变为 $-1$.

    在得到栈 $ops$ 之后，$sign$ 的取值就能够确定了：如果当前遇到了 $+$ 号，则更新 $sign\leftarrow ops.top()$ ；如果遇到了遇到了 $-$ 号，则更新 $sign\leftarrow -ops.top()$.

然后，每当遇到 $($ 时，都要将当前的 $sign$ 取值压入栈中；每当遇到 $)$ 时，都从栈中弹出一个元素。这样，我们能够在扫描字符串的时候，即时地更新 $ops$ 中的元素.

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
func calculate(s string) int {
	n := len(s)
	ans := 0
	ops := []int{1}
	sign := 1

	for i := 0; i < n; {
		switch s[i] {
		case ' ':
			i++
		case '-':
			sign = -ops[len(ops)-1]
			i++
		case '+':
			sign = ops[len(ops)-1]
			i++
		case '(':
			ops = append(ops, sign)
			i++
		case ')':
			ops = ops[:len(ops)-1]
			i++
		default:
			num := 0
			for ; i < n && '0' <= s[i] && s[i] <= '9'; i++ {
				num = num*10 + (int)(s[i]-'0')
			}
			ans += sign * num
		}
	}
	return ans
}

331. 验证二叉树的前序序列化「Medium」

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

1
2
3
4
5
6
7
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

示例 1:

1
2
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

1
2
输入: "1,#"
输出: false

算法分析：

方法一：栈
我们可以定义一个概念，叫做槽位。一个槽位可以被看作「当前二叉树中正在等待被节点填充」的那些位置。

二叉树的建立也伴随着槽位数量的变化。每当遇到一个节点时：

如果遇到了空节点，则要消耗一个槽位；

如果遇到了非空节点，则除了消耗一个槽位外，还要再补充两个槽位。

此外，还需要将根节点作为特殊情况处理。

p

我们使用栈来维护槽位的变化。栈中的每个元素，代表了对应节点处剩余槽位的数量，而栈顶元素就对应着下一步可用的槽位数量。当遇到空节点时，仅将栈顶元素减 $1$；当遇到非空节点时，将栈顶元素减 $1$ 后，再向栈中压入一个 $2$。无论何时，如果栈顶元素变为 $0$，就立刻将栈顶弹出。

历结束后，若栈为空，说明没有待填充的槽位，因此是一个合法序列；否则若栈不为空，则序列不合法。此外，在遍历的过程中，若槽位数量不足，则序列不合法。

  • 时间复杂度：$O(n)$.
  • 空间复杂度：$O(n)$.

方法二：计数

回顾方法一的逻辑，如果把栈中元素看成一个整体，即所有剩余槽位的数量，也能维护槽位的变化。

因此，我们可以只维护一个计数器，代表栈中所有元素之和，其余的操作逻辑均可以保持不变

  • 时间复杂度：$O(n)$.
  • 空间复杂度：$O(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
25
26
27
28
29
func isValidSerialization(preorder string) bool {
    n := len(preorder)
    stk := []int{1}
    for i := 0; i < n; {
        if len(stk) == 0 {
            return false
        }
        if preorder[i] == ',' {
            i++
        } else if preorder[i] == '#' {
            stk[len(stk)-1]--
            if stk[len(stk)-1] == 0 {
                stk = stk[:len(stk)-1]
            }
            i++
        } else {
            // 读一个数字
            for i < n && preorder[i] != ',' {
                i++
            }
            stk[len(stk)-1]--
            if stk[len(stk)-1] == 0 {
                stk = stk[:len(stk)-1]
            }
            stk = append(stk, 2)
        }
    }
    return len(stk) == 0
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isValidSerialization(preorder string) bool {
    n := len(preorder)
    slots := 1
    for i := 0; i < n; {
        if slots == 0 {
            return false
        }
        if preorder[i] == ',' {
            i++
        } else if preorder[i] == '#' {
            slots--
            i++
        } else {
            // 读一个数字
            for i < n && preorder[i] != ',' {
                i++
            }
            slots++ // slots = slots - 1 + 2
        }
    }
    return slots == 0
}

456. 132 模式「Medium」

给你一个整数数组 nums ，数组中共有 n 个整数。

132 模式的子序列 由三个整数 nums[i], nums[j] 和 nums[k] 组成

并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j]

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false

示例 1：

1
2
3
输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

1
2
3
输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

算法分析：

我们首先可以考虑枚举 132 模式中的 3

  • 由于 1 是模式中的最小值，因此我们在枚举 j 的同时，维护数组 num[0, j - 1] 中的最小值，因为只有 a[i] < a[j] 时，我们才可以选择 a[i] 作为 1.

  • 由于 2 是模式中的次小值，因此我们可以使用一个有序集合（例如平衡树）维护数组中右侧元素

    nums[j + 1, n - 1] 中的所有值。当我们确定了 a[i] 和 a[j] 时，我们就可以在有序集合中查询严格比 a[i] 大的那个最小元素，即为 a[k].

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
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }

        // 左侧最小值
        int left_min = nums[0];
        // 右侧所有元素
        multiset<int> right_all;

        for (int k = 2; k < n; ++k) {
            right_all.insert(nums[k]);
        }

        for (int j = 1; j < n - 1; ++j) {
            if (left_min < nums[j]) {
                auto it = right_all.upper_bound(left_min);
                if (it != right_all.end() && *it < nums[j]) {
                    return true;
                }
            }
            left_min = min(left_min, nums[j]);
            right_all.erase(right_all.find(nums[j + 1]));
        }

        return false;
    }
};

Chapter2 Tree

树的解决我们一般使用递归方法，递归概述如下：

  • 将问题转化为规模更小的子问题，直至边界情况
  • 递归方程 + 边界条件
  • 借助于计算机的程序栈，利用函数自身调用来实现

124. 二叉树中的最大路径和「Hard」

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

picture

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

picture

1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

算法分析：

首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下：

  • 空节点的最大贡献值等于 $0$.
  • 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和 ( 对于叶节点而言，最大贡献值等于节点值 )

例如，考虑如下二叉树。

1
2
3
4
5
 -10
 / \
9  20
  /  \
 15   7

叶节点 9、15、7 的最大贡献值分别为 9、15、7。

得到叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。

节点 20 的最大贡献值等于 20 + max(15, 7) = 35.

节点 -10 的最大贡献值等于 -10 + max(35, 9) = 25.

上述计算过程是递归的过程，因此，对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。

根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

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
class Solution {
private:
    int maxSum = INT_MIN;
public:
    int maxGain(TreeNode* root) {
        if (!root) return 0;
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(root->left), 0);
        int rightGain = max(maxGain(root->right), 0);
        
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = root->val + leftGain + rightGain;
        
        // 更新答案
        maxSum = max(maxSum, priceNewpath);
        
        // 返回节点的最大贡献值
        return root->val + max(leftGain, rightGain);
    }
    
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

剑指 Offer 26. 树的子结构「Medium」

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

1
2
3
4
5
    3
   / \
  4   5
 / \
1   2

给定的树 B：

1
2
3
  4 
 /
1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1
2
输入：A = [1,2,3], B = [3,1]
输出：false

算法分析：

  1. 双重递归第一重，isSubStructure
    • 判断 pRoot2 是否为 pRoot1 的子结构 (约定空树,不为任何一棵树的子结构)
    • 约定空树不是任意一个树的子结构. 所以 A 不可为空树,且 B 不可为空树。
    • B 是以 “A 为根节点“ 的子结构,或者 B 是 “A 的左子树“ 的子结构,或者B是 “A 的右子树“ 的子结构。注意三者为 或 的关系
    • 相当于对 A 进行了前序遍历: 根->左->右
  2. 双重递归第二重，isInclude
    • 判断 pRoot1 是否包含 pRoot2 (从集合关系分析,空集属于任何集合的子集)
    • pRoot2 为空,则 pRoot1 包含 pRoot2
    • pRoot1 为空,则 pRoot1 不包含 pRoot2
    • pRoot1，pRoot2 都不为空, 但节点值不同，则 pRoot1 不包含 pRoot2，即不具备包含关系
    • 如果值相同，则判断他们的左右节点是否也是包含关系（必须都是包含关系才行）
    • 递归判断 A 的左节点和 B 的左节点是否相等, 递归判断 A 的右节点和 B 的右节点是否相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A == nullptr) return false;
        if (B == nullptr) return false;
        return isInclude(A, B) or isSubStructure(A->left, B) or isSubStructure(A->right, B);
    }
    bool isInclude(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (pRoot2 == nullptr) return true;
        if (pRoot1 == nullptr) return false;
        if (pRoot1->val != pRoot2->val) return false;
        return isInclude(pRoot1->left, pRoot2->left) and 
          		 isInclude(pRoot1->right, pRoot2->right);
    }
};
#Programming #Data Structure
Leetcode Data Structure Note
https://www.mementos.top/1976/04/01/Leetcode Data Structure Note/
作者
Natsumi
发布于
1976年4月1日
许可协议