BM94. 接雨水问题
描述
示例1
输入:
[3,1,2,5,2,4]
输出:
5
说明:
数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。示例2
输入:
[4,5,1,3,2]
输出:
2
C++ 解法, 执行用时: 24ms, 内存消耗: 7308KB, 提交时间: 2021-04-19
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* max water
* @param arr int整型vector the array
* @return long长整型
*/
long long maxWater(vector<int>& arr) {
// write code here
int left = 0,right=arr.size()-1;
long long ans = 0;
int left_max = 0,right_max = 0;
while(left<right){
if(arr[left]<arr[right]){
arr[left]>=left_max ? (left_max = arr[left]):ans+=(left_max-arr[left]);
++left;
}
else{
arr[right] >= right_max ? (right_max = arr[right]): ans+=(right_max-arr[right]);
--right;
}
}
return ans;
}
};
C++ 解法, 执行用时: 24ms, 内存消耗: 7392KB, 提交时间: 2021-03-23
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
long long maxWater(vector<int>& arr) {
if(arr.size() <= 2) return 0;
long long res = 0;
int left = 0, right = arr.size() - 1;
int left_longest = 0, right_longest = 0;
while(left <= right) {
if(left_longest < right_longest) {
arr[left] >= left_longest ? left_longest = arr[left] : res += left_longest - arr[left];
left++;
}
else {
arr[right] >= right_longest ? right_longest = arr[right] : res += right_longest - arr[right];
right--;
}
}
return res;
}
};
C++ 解法, 执行用时: 24ms, 内存消耗: 7472KB, 提交时间: 2021-07-16
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* max water
* @param arr int整型vector the array
* @return long长整型
*/
long long maxWater(vector<int>& arr) {
int n = arr.size();
if(!n) return 0;
int l = 0, r = n - 1;
long long ans = 0;
while(l < r) {
int minx = min(arr[l], arr[r]);
while(l < r && arr[l] <= minx) {
ans += minx - arr[l];
l++;
}
while(l < r && arr[r] <= minx) {
ans += minx - arr[r];
r--;
}
}
return ans;
}
};
C++ 解法, 执行用时: 25ms, 内存消耗: 7292KB, 提交时间: 2021-09-11
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* max water
* @param arr int整型vector the array
* @return long长整型
*/
long long maxWater(vector<int>& arr) {
long long out = 0;
if(arr.size() < 3) return out;
int left = 0, right = arr.size() - 1;
while(left < right)
{
if(arr[left] < arr[right])
{
//int v = 0;
int left_v = arr[left];
while(arr[left] <= arr[right] && left < right)
{
if(arr[left] >= left_v) left_v = arr[left];
out += (left_v - arr[left]) > 0 ? (left_v - arr[left]) : 0;
left++;
}
}
else
{
//int v = 0;
int right_v = arr[right];
while(arr[left] >= arr[right] && left < right)
{
if(arr[right] >= right_v) right_v = arr[right];
//v = (right_v - arr[right]) > 0 ? (right_v - arr[right]) : 0;
out += (right_v - arr[right]) > 0 ? (right_v - arr[right]) : 0;
right--;
}
}
}
//cout << out <<endl;
return out;
}
};
C++ 解法, 执行用时: 25ms, 内存消耗: 7308KB, 提交时间: 2021-04-25
class Solution {
public:
/**
* max water
* @param arr int整型vector the array
* @return long长整型
*/
long long maxWater(vector<int>& arr) {
// write code here
long long left = 0;
long long right = arr.size()-1;
int min_num = min(arr[left], arr[right]);
long long result=0 ;
if(arr.size()<=2) return 0;
while(left<right){
if(arr[left]<=arr[right]){
left++;
if(min_num>arr[left]) result += min_num-arr[left];
else {
min_num = min(arr[left], arr[right]);
}
}
else {
right--;
if(min_num>arr[right]) result += min_num-arr[right];
else {
min_num = min(arr[left], arr[right]);
}
}
}
return result;
}
};
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();