c++解决这题,用单调栈: 给定一个大小为n×n的矩阵,矩阵中的每个位置只可能为0或1两个数值中的一个,且矩阵中恰好有n个1,且任意一行或一列中有且仅有一个1。对于一个大小为k×k(1≤k≤n)的子矩阵,若子矩阵中包含1的数量恰好为k个,则认为这个子矩阵是优美的。 现在请你统计出优美的子矩阵的数量。 输入格式: 输入的第一行包含一个整数n(1≤n≤5e4),表示矩阵的大小,矩阵中包含的11的数量。 接下来nn行,每行两个正整数xi,yi(1≤xi,yi≤n),表示矩阵的第xi行,第yi列的位置存在1。 输入保证每个xi和每个yi都是不同的,即矩阵的每行、每列中只有一个1。 输出格式: 输出优美的子矩阵的数量。 输入: 5 1 1 4 2 3 3 2 5 5 4 输出: 9
时间: 2024-04-06 13:28:53 浏览: 26
这个问题需要用到单调栈。
首先,对于每一行,我们可以维护一个高度数组,表示当前行往上延伸的连续1的个数。然后对于每一个子矩阵,我们可以通过枚举起始行和结束行来确定这个子矩阵的高度数组。
接下来,我们可以用单调栈来找到每个高度数组的最大子矩阵。对于每个高度数组,我们可以将它看作一个直方图。然后我们就可以用单调栈来找到最大的矩形面积。具体来说,我们维护一个单调递增的栈,每次遇到一个比栈顶元素小的元素时,我们就可以计算出以栈顶元素为高的最大矩形面积。具体实现时,我们可以将高度数组的两端各加入一个高度为0的元素,这样保证了最后栈一定会被清空。
最后,我们统计所有子矩阵的最大矩形面积之和即可得到答案。
代码如下:
相关问题
你能用C++完成下面的题目嘛:给定一个n*n的矩阵,输出他们顺时针旋转90度后的结果,注意,每个数的后面都有空格
当然可以!以下是C++代码:
```c++
#include <iostream>
using namespace std;
const int MAXN = 105;
int a[MAXN][MAXN];
int main() {
int n;
cin >> n;
// 读入矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
// 旋转90度
for (int j = 0; j < n; j++) {
for (int i = n - 1; i >= 0; i--) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
以上代码可以实现将一个n*n的矩阵顺时针旋转90度,并按照题目要求输出结果。
C++ 给定一个n x n的二维矩阵,请你将矩阵顺时针旋转90度并输出
这个问题属于技术问题,可以直接回答。将矩阵顺时针旋转90度可以通过先对矩阵进行转置,再对每一行进行反转来实现。具体实现方式可以参考以下代码:
```python
def rotate(matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
# 转置矩阵
n = len(matrix)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 反转每一行
for i in range(n):
matrix[i] = matrix[i][::-1]
# 输出旋转后的矩阵
for i in range(n):
for j in range(n):
print(matrix[i][j], end=' ')
print()
```
调用该函数,将传入的矩阵进行顺时针旋转90度,同时输出旋转后的矩阵:
```python
matrix = [[1,2,3],[4,5,6],[7,8,9]]
rotate(matrix)
```
输出结果为:
```
7 4 1
8 5 2
9 6 3
```
好笑的笑话:为什么程序员总是说"这很简单"?因为他们总是把复杂的问题拆分成简单的子问题。