Joyce' Blog
0%

maximal-rectangle & merge-sorted-array

发表于 更新于

题目描述

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

题解

暴力求解：主要的想法是，对于矩阵中的每一个元素，向上找：以其为右下顶点的矩形面积，找的过程中，矩形的长是这一列中最小的连续“1”的数量，宽是行数之差。需要一个辅助矩阵count，count[i][j]用来记录matrix[i][j]在i这一行前面连续的“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
30
31
32
33
34
35
36
37
38
39
int maximalRectangle(vector<vector<char>>& matrix) {
	int row = matrix.size();
	if (!row)return 0;
	int col = matrix[0].size();
	if (!col)return 0;
	vector<vector<int>> count;
	for (int i = 0; i < row; i++)
		count.push_back({ (matrix[i][0] - '0') });
	for (int i = 0; i < row; i++)
	{
		for (int j = 1; j < col; j++)
		{
			if (matrix[i][j - 1] == '0')
				count[i].push_back(matrix[i][j] - '0');
			else
				count[i].push_back(count[i][j - 1] + matrix[i][j] - '0');
		}
	}

	int res = count[0][0];
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			if (matrix[i][j] == '1')
			{
				int width = count[i][j];
				for (int k = i; k >= 0; k--)
				{
					if (matrix[k][j] == '0')break;
					width = count[k][j] < width ? count[k][j] : width;
					int area = width * (i - k + 1);
					res = area > res ? area : res;
				}
			}
		}
	}
	return res;
}

执行用时 :28 ms, 在所有 C++ 提交中击败了57.09%的用户

内存消耗 :12.3 MB, 在所有 C++ 提交中击败了13.35%的用户

借助单调栈：

1

还是用到了上面的count矩阵，从左往右竖着划分，可以看做有col个求最大矩形柱状面积的图。此时count[i][j]就表示在第j列时，第i个柱子的高度。

对于单个求largestRectangleArea的情况，可以借助单调递增栈来解决，当柱子的高度递增时，将i入栈，若当前高度更小，则需要将i弹出栈直到不违背递增性质。在弹出栈的过程中需要算面积。为了编程方便，可以在一开始将高度0插入到第一个柱子之前。

附

C++ template：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <int DIM, typename T>
class DotProduce{
    public:
    static T result (T* a, T* b){
        return *a * *b + DotProduce<DIM-1, T>::result(a+1, b+1);
    }
};

//The end criterion is the case of a one-dimensional vector:
template <typename T>
class DotProduce<1, T>{
    public:
    static T result (T* a, T* b){
        return *a * *b;
    }
};

Thus, for

1
dot_produce<3>(a,b)

the instantiation process computes the following:

1
2
3
4
DotProduce<3, int>::result(a, b)
    = *a * *b + DotProduce<2, int>::result(a+1, b+1)
    = *a * *b + (*(a+1) * *(b+1) + DotProduce<1, int>::result(a+2, b+2))
    = *a * *b + (*(a+1) * *(b+1) +(*(a+2) * *(b+2)))

元编程（Metaprogramming）是指某类计算机程序的编写，这类计算机程序编写或者操纵其他程序（或者自身）作为它们的数据，或者在运行时完成部分本应在编译时完成的工作。 很多情况下与手工编写全部代码相比工作效率更高。

volatile关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改。

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

题解

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
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	if (m == 0) { nums1 = nums2; return;}
	if (n == 0)return;
	vector<int> v;
	int k1 = 0, k2 = 0;
	while (true)
	{
		if (nums1[k1]<= nums2[k2])
		{
			v.push_back(nums1[k1]);
			k1++;
			if (k1 == m)break;
		}
		else
		{
			v.push_back(nums2[k2]);
			k2++;
			if (k2 == n)break;
		}
	}
	while (k2!=n)
		v.push_back(nums2[k2++]);
	while (k1 != m)
		v.push_back(nums1[k1++]);
	nums1 = v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	if (m == 0) { nums1 = nums2; return; }
	if (n == 0)return;
	int k = 0;
	auto it2 = nums2.begin();
	while (true)
	{
		if (*it2 <= nums1[k])
		{
			it2++;
			if (it2 == nums2.end())break;
		}
		else
		{
			it2 = nums2.insert(it2, nums1[k]);
			k++;
			if (k == m)break;
		}
	}
	while (k < m)nums2.push_back(nums1[k++]);
	nums1.clear();
	nums1 = nums2;
}