資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中蛋糕水平和垂直切割後的最大面積
假設我們有一個矩形蛋糕，高度為 h，寬度為 w，我們還有兩個整數陣列 horizontalCuts 和 verticalCuts，其中 horizontalCuts[i] 表示從矩形蛋糕頂部到第 i 個水平切割的距離，類似地，verticalCuts[j] 表示從矩形蛋糕左側到第 j 個垂直切割的距離。
我們必須找到在我們在 horizontalCuts 和 verticalCuts 陣列中提供的每個水平和垂直位置切割蛋糕後，蛋糕碎片的最大面積。答案可能很大，因此返回此結果模 10^9 + 7。
因此，如果輸入類似於 h = 5，w = 4，horizontalCuts = [1,2,4]，verticalCuts = [1,3]
則輸出將為 4，從該影像我們可以理解給定的矩形蛋糕。
紅線是水平和垂直切割。我們切割蛋糕後，綠色蛋糕碎片的面積最大。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 mul()，它將接收 a、b，
返回 ((a mod m) * (b mod m)) mod m
從主方法中，我們將獲取 h、w、陣列 hh、陣列 vv，
對陣列 hh 和 vv 進行排序
將 hh 的第一個元素插入到 hh 的索引 0 處
在 hh 的末尾插入 h
將 vv 的第一個元素插入到 vv 的索引 0 處
在 vv 的末尾插入 w
a := 0，b := 0
對於初始化 i := 1，當 i < hh 的大小，更新（i 增加 1），執行：
a := a 和 hh[i] - hh[i - 1] 的最大值
對於初始化 i := 1，當 i < vv 的大小，更新（i 增加 1），執行：
b := b 和 vv[i] - vv[i - 1] 的最大值
返回 mul(a, b)
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long int lli;
class Solution {
public:
lli mul(lli a, lli b){
return ((a % mod) * (b % mod)) % mod;
}
int maxArea(int h, int w, vector<int>& hh, vector<int>& vv) {
sort(hh.begin(), hh.end());
sort(vv.begin(), vv.end());
hh.insert(hh.begin(), 0);
hh.push_back(h);
vv.insert(vv.begin(), 0);
vv.push_back(w);
int a = 0;
int b = 0;
for (int i = 1; i < hh.size(); i++) {
a = max(a, hh[i] - hh[i - 1]);
}
for (int i = 1; i < vv.size(); i++) {
b = max(b, vv[i] - vv[i - 1]);
}
return mul(a, b);
}
};
main(){
Solution ob;
vector<int> v = {1,2,4}, v1 = {1,3};
cout << (ob.maxArea(5,4,v,v1));
}輸入
5,4,{1,2,4}, {1,3}輸出
4
159 次檢視
