0%

单调栈

发表于 分类于

单调栈结构

应用: 得到一个数组左边和右边每个位置左边和右边离它最近并且比它大的值

解释:

  1. 创建一个栈.
  2. 如果栈为空, 将索引压栈.
  3. 如果栈顶索引对应的值大于当前元素, 将索引压栈.
  4. 如果等于, 合并索引.
  5. 如果大于, 弹栈, 得到弹出的元素, 此时当前索引为右边第一个比弹出元素索引大的值, 栈顶元素为左边第一个比弹出元素大的值, 如果栈为空, 左边不存在比当前元素大的值.
  6. 循环结束, 依次弹栈, 每次弹出元素的右边没有比它大的值, 栈顶元素为左边第一个比弹出元素大的值, 如果栈为空, 左边不存在比当前元素大的值.

代码:

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
33
34
35
36
37
vector<pair<int, int>>  monotone_priority_stack(vector<int>& arr)
{
	vector<pair<int, int>> res(arr.size(), make_pair(-1, -1));
	stack<list<int>> s;
	for (int i = 0; i < arr.size(); ++i)
	{
		while (!s.empty() && !s.top().empty() && arr[i] > arr[*s.top().begin()])
		{
			list<int> index = s.top();
			s.pop();
			for (int item : index)
			{

				res[item].first = !s.empty() && !s.top().empty() ? *(--s.top().end()) : -1;
				res[item].second = i;
			}
		}
		if (!s.empty() && !s.top().empty() && arr[i] == arr[*s.top().begin()])
		{
			s.top().push_back(i);
		}
		else
		{
			s.push(list<int>(1, i));
		}
	}
	while (!s.empty())
	{
		list<int> index = s.top();
		s.pop();
		for (int item : index)
		{
			res[item].first = !s.empty() && !s.top().empty() ? *(--s.top().end()) : -1;
		}
	}
	return res;
}

问题: 给定一个无序数组, 返回由这个数组元素组成的树, 要求这颗树的所有子树的根节点的值是这颗子树的最大值, 数组内不含重复元素

思路:

  1. 使用单调栈计算出数组每个元素左边和右边第一个比它大的元素.
  2. 每个元素的父节点为离他最近较小的那个比它大的元素.
  3. 根节点是最大的元素.

代码:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution
{
	protected internal class TreeNode
	{
		public TreeNode(int value)
		{
			this.Value = value;
		}
		public int Value { get; set; }
		public TreeNode Left { get; set; }
		public TreeNode Right { get; set; }
	}


	public static TreeNode GetTree(params int[] arr)
	{
		Stack<int> stack = new Stack<int>();
		Tuple<int, int>[] maxIndex = new Tuple<int, int>[arr.Length];
		for (int i = 0; i < arr.Length; i++)
		{
			while (stack.Count != 0 && arr[stack.Peek()] < arr[i])
			{
				int index = stack.Pop();
				maxIndex[index] = new Tuple<int, int>(stack.Count == 0 ? -1 : stack.Peek(), i);
			}
			stack.Push(i);
		}
		while (stack.Count != 0)
		{
			int index = stack.Pop();
			maxIndex[index] = new Tuple<int, int>(stack.Count == 0 ? -1 : stack.Peek(), -1);
		}
		TreeNode root = null;
		Dictionary<int, TreeNode> nodes = new Dictionary<int, TreeNode>();
		for (int i = 0; i < maxIndex.Length; i++)
		{
			if (!nodes.ContainsKey(i))
			{
				nodes[i] = new TreeNode(arr[i]);
			}
			var (left, right) = maxIndex[i];
			if (left == -1 && right == -1)
			{
				root = nodes[i];
			}
			else if (left != -1 && right != -1)
			{
				if (arr[left] < arr[right])
				{
					if (!nodes.ContainsKey(left))
					{
						nodes[left] = new TreeNode(arr[left]);
					}
					nodes[left].Right = nodes[i];
				}
				else
				{
					if (!nodes.ContainsKey(right))
					{
						nodes[right] = new TreeNode(arr[right]);
					}
					nodes[right].Left = nodes[i];
				}
			}
			else
			{
				if (left != -1)
				{
					if (!nodes.ContainsKey(left))
					{
						nodes[left] = new TreeNode(arr[left]);
					}
					nodes[left].Right = nodes[i];
				}
				else
				{
					if (!nodes.ContainsKey(right))
					{
						nodes[right] = new TreeNode(arr[right]);
					}
					nodes[right].Left = nodes[i];
				}
			}

		}
		return root;
	}
}

题目: 求最大子矩阵的大小

  • 给定一个整型矩阵map, 其中的值只有0和1两种, 求其中全是1的所有矩阵区域中, 最大矩阵区域为1的数量.
  • 例如, 矩阵:
    1
    2
    3
    4
    5
    /*
    	1 0 1 1
    	1 1 1 1
    	1 1 1 0
    */
    其中, 最大的矩形区域有6个1, 所以返回6.

思路:

  1. 遍历每一行, 遍历到某个数的时候, 如果这个数不是0, 加上上一行同位置的数.
  2. 每个数求左右离它最近的比它小的数.
  3. 计算每一行作为底的个数.
  4. 每次记录每一行的最大值
  5. 取所有最大值的最大值

代码:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public static int GetMaxOne(int[][] arr)
{
	if (arr == null)
	{
		return 0;
	}
	int res = 0;
	for (int i = 0; i < arr.Length; i++)
	{
		Stack<List<int>> stack = new Stack<List<int>>();
		Tuple<int, int>[] minIndex = new Tuple<int, int>[arr[i].Length];
		for (int j = 0; j < arr[i].Length; j++)
		{
			if (i > 0 && arr[i][j] != 0)
			{
				arr[i][j] += arr[i - 1][j];
			}
			while (stack.Count != 0 && stack.Peek().Count != 0 && arr[i][stack.Peek()[0]] > arr[i][j])
			{
				List<int> set = stack.Pop();
				foreach (int item in set)
				{
					minIndex[item] =new Tuple<int, int>(stack.Count != 0 && stack.Peek().Count != 0 ? stack.Peek()[stack.Peek().Count - 1] : -1, j);
				}
			}
			List<int> list = new List<int>();
			list.Add(j);
			stack.Push(list);
		}
		while (stack.Count != 0)
		{
			List<int> set = stack.Pop();
			foreach (int item in set)
			{
				minIndex[item] = new Tuple<int, int>(stack.Count != 0 && stack.Peek().Count != 0 ? stack.Peek()[0] : -1, -1);
			}
		}
		int max = int.MinValue;
		for (int j = 0; j < minIndex.Length; j++)
		{
			(int left, int right) = minIndex[j];
			max = Math.Max(max, arr[i][j] * (right - left - 1));
		}
		res = Math.Max(res, max);
	}
	return res;
}