AI刷题-最大矩形面积问题、小M的数组变换

目录

一、最大矩形面积问题

问题描述

输入格式

输出格式

输入样例

输出样例

数据范围

解题思路： 

问题理解

数据结构选择

算法步骤

最终代码： 

运行结果： 

二、小M的数组变换 

问题描述

测试样例

解题思路：

问题理解

关键点

解题思路

算法步骤

最终代码： 

运行结果： 

 

---

一、最大矩形面积问题

问题描述

对于一个有 N 个元素的数组，包含如下的元素 h1, h2, ..., hn，对于 k 个相邻的元素，我们定义它的最大面积如下：
R(k)=k∗min(h[i],h[i+1],....,h[i+k−1])R(k)=k∗min(h[i],h[i+1],....,h[i+k−1])

求 R(k) 的最大值

输入格式

总共有两行，第一行是数组长度 N，第二个是空格分割的所有数组的内容

输出格式

输出 R(k) 的最大值

输入样例

5
1 2 3 4 5

输出样例

9

数据范围

• 1 <= N <= 10^5
• 1 <= h[i] <= 10^6

解题思路： 

问题理解

我们需要在一个数组中找到一个长度为 k 的子数组，使得这个子数组的最小值乘以 k 的值最大。换句话说，我们需要最大化 R(k) = k * min(h[i], h[i + 1], ..., h[i + k - 1])。

数据结构选择

由于数组的长度 N 最大可以达到 10^5，我们需要一个高效的算法来解决这个问题。我们可以考虑使用滑动窗口（Sliding Window）技术来遍历所有可能的子数组，并使用一个数据结构来快速找到窗口内的最小值。

算法步骤

1. 初始化：定义一个变量 max_area 来存储当前找到的最大面积。
2. 滑动窗口：使用两个指针 left 和 right 来表示当前窗口的左右边界。
3. 计算最小值：在每次移动窗口时，计算当前窗口内的最小值。
4. 更新最大面积：计算当前窗口的最小值乘以窗口长度 k，并与 max_area 比较，更新 max_area。
5. 移动窗口：将窗口向右滑动一个位置，继续上述步骤，直到遍历完整个数组。

最终代码： 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int solution(int n, std::vector<int> A) {int max_area = 0;// 遍历所有可能的 kfor (int k = 1; k <= n; ++k) {// 遍历所有可能的起始位置 ifor (int i = 0; i <= n - k; ++i) {// 计算当前 k 个元素的最小值int min_height = *min_element(A.begin() + i, A.begin() + i + k);// 计算当前的面积int area = k * min_height;// 更新最大面积max_area = max(max_area, area);}}return max_area;
}int main() {// 添加测试用例std::vector<int> A_case1 = std::vector<int>{1, 2, 3, 4, 5};std::cout << (solution(5, A_case1) == 9) << std::endl;return 0;
}

运行结果： 

二、小M的数组变换 

问题描述

小M拿到一个数组，她可以进行多次操作，每次操作可以选择两个元素 aiai​ 和 ajaj​，并选择 aiai​ 的一个因子 xx，然后将 aiai​ 变为 ai/xai​/x，并将 ajaj​ 变为 aj×xaj​×x。她的目标是通过有限次操作，使得数组中的每个元素最多只包含一种素因子。

素因子的定义是：若 xx 能被素数 pp 整除，那么 pp 是 xx 的一个素因子。例如，1212 的素因子有 22 和 33。

你的任务是判断是否有可能通过有限次操作，使数组中的每个元素最多只包含一种素因子。如果可以，输出 "Yes"，否则输出 "No"。

---

测试样例

样例1：

输入：n = 4 ,a = [1, 2, 3, 4]
输出：'Yes'

样例2：

输入：n = 2 ,a = [10, 12]
输出：'No'

样例3：

输入：n = 3 ,a = [6, 9, 15]
输出：'Yes'

解题思路：

问题理解

我们需要判断是否可以通过有限次操作，使得数组中的每个元素最多只包含一种素因子。每次操作可以选择两个元素 ai​ 和 aj​，并选择 ai​ 的一个因子 x，然后将 ai​ 变为 ai​/x，并将 aj​ 变为 aj​×x。

关键点

1. 素因子分解：每个数都可以分解为若干个素因子的乘积。例如，12 可以分解为 2 * 2 * 3。
2. 操作的本质：通过操作，我们可以将一个数的素因子转移到另一个数上。
3. 目标：最终每个数只包含一种素因子。

解题思路

1. 素因子集合：首先，我们需要找出每个数的所有素因子。
2. 素因子图：将每个数的素因子看作图中的节点，如果两个数共享同一个素因子，则在它们之间建立一条边。
3. 连通性：如果这个图是连通的，那么我们可以通过操作将所有素因子集中到某些数上，使得每个数只包含一种素因子。
4. 判断连通性：可以使用并查集（Union-Find）来判断图的连通性。

算法步骤

1. 素因子分解：对每个数进行素因子分解，记录每个数的素因子集合。
2. 构建并查集：将每个素因子作为一个节点，如果两个数共享同一个素因子，则将它们对应的素因子节点进行合并。
3. 判断连通性：最终判断并查集中是否只有一个连通分量。

最终代码： 

#include <bits/stdc++.h>
using namespace std;
string solution(int n,vector<int>& a)
{set<int> st;for (auto&& ai : a){int sai = ceil(sqrt(ai));for(int j=2;j<=ai && j<=sai;j++){while(ai%j == 0){ai /= j;st.insert(j);}}if(ai != 1) st.insert(ai);}return st.size()<=a.size() ? "Yes" : "No";
}int main() {vector<int> a1 = {1, 2, 3, 4};vector<int> a2 = {10, 12};vector<int> a3 = {6, 9, 15};cout << (solution(4, a1) == "Yes") << endl;cout << (solution(2, a2) == "No") << endl;cout << (solution(3, a3) == "Yes") << endl;return 0;
}

运行结果：